Dijkstra Algorithm (다익스트라)

다익스트라 알고리즘

하나의 정점을 기준으로 나머지 모든 정점까지의 최소비용을 구한다.

 

1. vector<pair<int,int>> graph[V] 에 간선 정보 저장함.

   graph[2] = pair(1,10)이면 2노드에서 1노드까지 10 가중치의 간선 존재

 

2. 시작 노드에서 시작.

 

3. 현재 노드에서 갈수 있는 노드 중 가중치가 가장 작은 노드 방문.

 

4. 해당 노드 거쳐 가는 거리 계산하고 최소값 갱신. 

(반복) 

 

 

3번을 수행할때 우선순위 큐가 쓰이는데 우선순위 큐를 쓰지 않아도 되긴한다.

그럴 경우 그냥 인접한 노드를 모두 방문해도 최종적으로 우리가 원하는 값을 얻을수는 있지만 이 경우 하나의 노드를 방문할때마다 인접한 모든 노드를 방문해야 한다.