[algorithm] Dijkstra 알고리즘

1. Dijkstra 알고리즘

• 시작 정점(Vertex)에서 거리가 최소인 정점(Edge)을 선택해 나가면서 최단 경로를 구하는 방식이다.
• 그리디 알고리즘을 사용했다.
• MST(최소 신장 트리)의 Prim 알고리즘과 구현방법이 유시하다.
• 음의 가중치가 없는 그래프에서만 사용 가능하다.

2. pseudo code

1  function Dijkstra(Graph, source):
 2
 3      create vertex set Q
 4
 5      for each vertex v in Graph:    // 초기화
 6          dist[v] ← INFINITY           // 소스에서 v까지의 아직 모르는 길이
 7          prev[v] ← UNDEFINED          // 소스에서 최적 경로의 이전 꼭짓점
 8          add v to Q                   // 모든 노드는 초기에 Q에 속해있다 (미방문 집합)
 9
10      dist[source] ← 0               // 소스에서 소스까지의 길이
11
12      while Q is not empty:
13          u ← vertex in Q with min dist[u]   // 최소 거리를 갖는 꼭짓점
14                                             // 을 가장 먼저 선택한다
15          remove u from Q
16
17          for each neighbor v of u:           // v는 여전히 Q에 있다.
18              alt ← dist[u] + length(u, v)
19              if alt < dist[v]:               // v 까지의 더 짧은 경로를 찾았을 때
20                  dist[v] ← alt
21                  prev[v] ← u
22
23      return dist[], prev[]
        

3. 알고리즘 적용 예시

1. 초기