Dijkstra's algorithm(다익스트라 알고리즘)

  Dijkstra's algorithm은 graph의 node 사이의 shortest path를 찾는 알고리즘입니다.

pseudocode 는 다음과 같습니다.

 1  function Dijkstra(Graph, source):
 2
 3      create vertex set Q
 4
 5      for each vertex v in Graph:             // Initialization
 6          dist[v] ← INFINITY                  // Unknown distance from source to v
 7          prev[v] ← UNDEFINED                 // Previous node in optimal path from source
 8          add v to Q                          // All nodes initially in Q (unvisited nodes)
 9
10      dist[source] ← 0                        // Distance from source to source
11      
12      while Q is not empty:
13          u ← vertex in Q with min dist[u]    // Node with the least distance will be selected first
14          remove u from Q 
15          
16          for each neighbor v of u:           // where v is still in Q.
17              alt ← dist[u] + length(u, v)
18              if alt < dist[v]:               // A shorter path to v has been found
19                  dist[v] ← alt 
20                  prev[v] ← u 
21
22      return dist[], prev[]

출처 : https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

dist[u]는 u의 source로 부터의 거리를 나타내며 prev[u] 는 u로 가는 최적화된 길에서 u 이전의 노드를 나타낸다.

12      while Q is not empty:
13          u ← vertex in Q with min dist[u]    // Node with the least distance will be selected first
14          remove u from Q 
15          
16          for each neighbor v of u:           // where v is still in Q.
17              alt ← dist[u] + length(u, v)
18              if alt < dist[v]:               // A shorter path to v has been found
19                  dist[v] ← alt 
20                  prev[v] ← u 

이 부분이 알고리즘의 핵심이다.

 u ← vertex in Q with min dist[u]

는 Q에 남아있는 노드 중에 dist[u]가 가장 짧은 노드를 찾아 반환하여 u에 저장한다. 그리고 Q에서 u를 제거한다.

16          for each neighbor v of u:           // where v is still in Q.
17              alt ← dist[u] + length(u, v)
18              if alt < dist[v]:               // A shorter path to v has been found
19                  dist[v] ← alt 
20                  prev[v] ← u 

이 부분에서는 (u, v) 로 가는 path가 존재하고 dist[v]가 dist[u] + (u, v)로 가는 path의 길이의 합보다 크면 dist[v]를 dist[u] + length(u, v)로 바꾼 후에 prev[v]에 u를 저장한다.

이것으로 dijkstra's algorithm이 완성되었습니다. 제가 한 부분은 그저 pseudocode를 읽어주는 것 밖에 안했지만 dijkstra's algorithm은 shortest path problem을 해결하기에 유용한 쉬운 알고리즘이라고 생각합니다. 한 번 코드를 작성해보시는 것을 추천합니다.(그리 어렵지 않아요.)