다익스트라 알고리즘

다익스트라 알고리즘? (Dijkstra Algorithm)

• 가중치 그래프(weighted graph)에서 두 정점(vertex) 사이의 최단 경로를 구하는 알고리즘
• A Shortest Path Algorithm
• 가중치가 양수일 경우에 사용

의사코드

function Dijkstra(Graph, source):

      create vertex set Q
      //방문하지 않은 노드들의 집합 Q 선언

      for each vertex v in Graph:       // 초기화
          dist[v] := INFINITY           // 소스에서 v까지의 아직 모르는 길이
          prev[v] := UNDEFINED          // 소스에서 최적 경로의 이전 꼭짓점
          add v to Q                    // 초기에는 모든 노드를 방문하지 않았기 때문에 Q에 add함.

      dist[source] := 0                  // 출발지 노드에서 출발지 노드까지의 거리 = 0

      while Q is not empty:                        // 방문하지 않은 노드들이 없을 때까지 반복.
          u := vertex in Q with min dist[u]        // u = Q 집합에서 거리(가중치)가 가장 작은 정점
          remove u from Q                          // Q 집합에서 u를 제거

          for each neighbor v of u:           // u의 모든 이웃 정점 v에 대해
              alt := dist[u] + length(u, v)   // alt = (출발지에서 u까지의 거리) + (u에서 v까지의 거리)
              if alt < dist[v]:               // 만약 v까지의 최소 거리가 alt보다 크다면
                  dist[v] := alt              // v까지의 최소 거리를 alt로 변경.
                  prev[v] := u                // 제일 가까운 노드는 u로 변경.

      return dist[], prev[]    

위키백과 다익스트라 알고리즘 의사코드 인용

 

그림 설명

그림 1. 가중치 그래프 예시

1. 시작 정점 //(a//)의 초기 거리값은 0으로 설정하고 나머지 //(b,c,d,e,f,z//)의 거리값은 //( \infty //)로 설정한다.
2. //(a//)의 이웃 정점인 //(b, c //)에 대한 거리값을 계산한다. //(b//)는 //( \infty //)에서 4, //(c//)는 //( \infty //)에서 2가 되고 방문한 노드의 집합에 //(S = {a, c}//)가 들어 간다. 
3. //(c//)에서 각각 //(b,d,e//)에 대한 거리값을 계산한다. 이 때, 원래 //((a-b)//) 거리값이 4였는데, 더 작은값인 //((a-c-b)//)가 //(2+1=3//)이므로 b의 거리값을 3으로 수정한다. 방문한 노드의 집합에는 //(S = {a, c, b}//)가 들어 간다. 
4. 이런식으로 인접 노드들의 최소 거리를 계산하며 방문한 노드 집합 //(S //)에 //(z//)가 있을 때까지 반복한다.

위의 의사코드와는 약간 다른 방법이다.

Notation

학교에서 강의를 들을 땐, 위의 의사코드와 달리 다른 표기법들이 있어서 정리한다.

• //( u //) : 가장 최근에 //( S_{k-1} //)에 추가된 정점
• //( v //) : //( S_{k-1} //)에 속하지 않는 정점
• //( S_{k} //) : k번째 반복일 때, 방문한 노드들의 집합 (위에선 미방문 노드들의 집합을 통해 반복했지만, 학교 강의에선 방문 노드들의 집합에 목적지 //(z//) 노드가 포함될 때 동안 반복)
• //( L_{k} //) : The length of shortest path from a to the vertices. (정점으로부터 가장 짧은 길이)
• //( L_{k}(a,v) //) : //( min(L_{k-1}(a,v), L_{k-1} + w(u, v)) //)
• //( w(u, v) //) : //(u//)와 //( v//)를 끝점으로 하는 모서리 길이