다익스트라

벨만포드에 이어서 최단경로를 찾는 알고리즘 중 하나다

최소스패닝트리 알고리즘과 비슷하게 check 배열을 둬서, 선택된 인덱스와 선택되지 않는 인덱스를 비교해서 그 거리를 계속 갱신해주는 형태다

따라서 모든 정점을 check 해야므로 V의 시간이 걸리고, check 해야하는 인덱스를 고르기 위해 모든 정점을 탐색해야므로 V의 시간이 덤으로 걸린다

따라서 다익스트라의 시간복잡도는 O(V*V)가 된다

 

1. check 되어있지않은 정점 중 가장 거리가 짧은 정점을 선택한다

2. 선택된 정점에 대해서 거리를 update한다