다익스트라(Dijkstra) 알고리즘 정의 및 살펴보기

이 게시글은 강원대학교 컴퓨터정보통신공학전공에서 2010년 봄학기 알고리즘 강의시간에 참고한 서적의 정보를 기반으로 작성되었습니다.

이 알고리즘은 1959년 다익스트라(Dijkstra)가 고안하였다.
이것은 어떠한 간선도 음수 값을 가지지 않는 방향그래프에서
주어진 출발점과 도착점 사이의 최단 경로 문제를 푸는 알고리즘!!

예를 들어, 그래프의 점들이 각각 지하철 역을 나타내고 연결선들이 지하철 노선을 의미한다면 이 알고리즘은 지하철 역간의 최단 경로를 구하게 된다.

아래 알고리즘에서 u := Extract_Min(Q)는 점의 집합 Q에서 가장 작은 d[u]값을 찾은 다음 그 점 u를 Q에서 제거한 후 반환하는 함수를 가리킨다.

function Dijkstra(G, w, s)for each vertex v in V[G]    // 초기화         d[v] := infinity         previous[v] := undefined    d[s] := 0   S := empty set   Q := set of all vertices   while Q is not an empty set  // 알고리즘의 실행         u := Extract_Min(Q)         S := S union {u}         for each edge (u,v) outgoing from u               if d[v] > d[u] + w(u,v)   // (u,v)의 경감                     d[v] := d[u] + w(u,v)                     previous[v] := u    //경로 추적할 때 쓰임

만약 모든 v에 대해서가 아니라 특정한 s에서 v까지의 최단 거리만을 알고 싶다면 9번째 행에서 u = t일 때 종료하면 된다.
s에서 t까지의 최단 경로는 다음과 같이 얻을 수 있다.

S := empty sequence
u := t
while defined u                                       
      insert u to the beginning of S
      u := previous[u]

di[start]=0; 
    for(i=1;i<=n;i++){
        min=MAX_INT;
        for(j=1;j<=n;j++){
            if(min>di[j] && chk[j]==0){
                min=di[j];
                w=j; 
            }
        }
    if(min==MAX_INT) break;
    chk[w]=1;
    for(j=1;j<=n;j++){
        if((a[j][w]!=0)&&di[j]>a[j][w]+di[w])
            di[j]=a[j][w]+di[w];
    }
}

위 두개의 코드는 위키피디아에서 발췌한 것임을 밝힌다.     위키피디아 본문 보기
그리고 아래는 교재에 등재된 알고리즘이다.

정수 n(>=2)과 정점이 n개 있는 연결된 가중치포함 방향그래프.
이 그래프는 2차원 배열 W로 표현되며, 행과 열의 인덱스는 각각 1부터 n까지 이다.
여기서 W[i][j]는 i번째 정점에서 j번째 정점을 잇는 이음선상의 가중치가 된다.

void dijkstra(int n, const number W[][], set_of_edges& F){
 index i, vnear;
 edge 3;
 index touch[2..n];
 number length[2..n];

 F = 0;

 for(i=2; i<=n; i++){  // 각 정점에 대해서 v1에서 출발하는 현재
  touch[i] = 1;   // 최단경로의 마지막 정점을 v1으로 초기화
  length[i] = W[1][i]; // 그 경로의 길이는
 }       // v1에서의 이음선상의 가중치로 초기화한다.

 repeat(n-1 times){    // n-1개 정점을 모두 Y에 추가
  min = ∞;
  for(i=2; i<=n; i++){  // 최단경로를 갖는지 각 정점을 점검한다.
   if(0<= length[i] <min){
    min = length[i];
    vnear = i;
   }
  }
  e = touch[vnear]가 인덱스인 정점에서 vnear가 인덱스인 정점으로 가는 이음선;
  e를 F에 추가;
  for(i=2; i<=n; i++){
   if(length[vnear] + W[vnear][i] < length[i]){
    length[i] = length[vnear]+W[vnear][i];
    touch[i] = vnear; // Y에 속하지 않는 각 정점에 대해서,
   }      // 최단 경로를 바꾼다.
  }
  length[vnear] = -1;   // vnear가 인덱스인 정점을 Y에 추가한다.
 }
}