최단경로 알고리즘

*** 하나의 정점에서 다른 모든 정점까지의 최단 경로 ***

최단경로(ShortestpPath)는 v(시작정점)에서부터 t(목표점)까지의 경로로서 이 경로를 구성하는 아크(간선)들의 가중치 합이 최소가 되는 경로를 말한다.

가중치는 비용, 길이, 시간, 거리 등과 같은 뜻이다.

하나의 아크로 된 경로의 가중치 합보다 두개나 혹은 세개의 아크로 된 경로의 가중치 합이 작을수도 있다.

이러한 모든 경로를 길이의 순서로 나타내는것이 최단경로 알고리즘이라고 할수 있다.

먼저 S를 최단 경로가 이미 찾아져서 확정된 정점의 집합이라 하자.

처음에는 이 S에 시작점 v만 포함시킨다.

이 S에 포함되지 못한 정점 i에 대해 Dist[i]는 시작점 v에서부터 S에 포함되어 있는 정점만을 경유하여 정점 i에 이르는 현재까지 알려진 최단경로의 거리라 하자.

그러면, 처음에 S에는 시작점 v만 포함되어 있고 Dist[v]의 값은 0이 된다.

알고리즘은 변수 u로 하여금 가장 최근에 이 S에 첨가된 노드를 가리키도록 한다.

처음에는 u에 v를 지정(u -> v)한다.

정점 u가 S에 첨가될 때마다 S에 포함되지 않은 u의 모든 인접 정점w에 대해 Dist[w]를 다시 계산한다.

그래서 만일 Dist[u]+weight(u, w)가 현재의 Dist[w]보다 작으면 Dist[w]의 값을 이 작은 값으로 대체한다.

왜냐하면, 지금까지 찾아낸 Dist[w]보다 새로 확정된 u를 경유하는 이 Dist[u] + weight(u, w)가 최단 경로가 되기 때문이다.

이와 같이 u의 모든 인접 정점에 대한 최단 거리 계산을 다하고 나면 이 Dist에 있는 모든 Dist[j]는 현재까지 v에서 j까지 S에 포함된 정점만을 경유한 최단 경로가 된다.

이때, 만일 S에 포함되지 않은 정점들에 대한 최단 경로 중에서 정점 w의 Dist[w]가 가장 작다고 하자.

그렇다면, 이 정점 w는 아직 S에 들어가지는 못했지만 시작점 v에서부터 w까지 어떤 다른 경로도 이 Dist[w]보다 더 작을 수 없다는 것을 의미한다.

왜냐하면, Dist[w]는 이미 S에 있는 정점만을 경유하는 w까지의 최단 경로이고, S에 포함되지 않은 어떤 정점 x를 경유하는 w까지의 경로는 그 길이가 이보다 긴 것이 틀림없기 때문이다.

그 이유는 S에 포함되지 않은 정점 x의 Dist[x]는 S에 포함되어 있는 어느 정점 y의 Dist[y]보다 분명히 크기 때문이다.

따라서, 정점 w에 대한 거리는 최단 경로 길이로 확정되고 정점 w는 S에 첨가된다.

이렇게 정점 w에 대한 최단 경로를 확정한 다음에는 다시 u <- w로 하고 앞에서 수행한 계산 과정, 즉 S에 포함되지 않은 u의 인접 정점에 대한 거리 계산을 다시 반복한다.

(이 연산 과정은 모든 정점에 대한 최단 경로가 결정될 때까지 수행한다.)

알고리즘 작성을 위해 그래프 G의 n개의 정점을 0에서 n-1까지 번호를 붙인다.

집합 S는 불리언(Boolean) 배열로 정점 i가 S[]에 포함되어 있으면 S[i] = true이고 아니면 S[i] = false로 표현한다.

그래프는 가중치 인접행렬 weight[n, n]으로 표현한다.

여기서 weight[i, j]는 아크 <i, j>의 가중치가 된다.

아크 <i, j>가 그래프 G에 포함되어 있지 않으면 weight[i, j]의 가중치로는 취급할 수 없는 아주 큰 값(999)으로 표현한다.

이 최단 경로를 찾아내는 Dijkstra의 ShortestPath의 알고리즘은 다음과 같다.

ShortestPath(v, weight, n) // v는 시작점, weight는 가중치 인접 행렬, n은 정점수

                                    // create S[n], Dist[n]

for(i←0; i<n; i←i+1) do {

       S[i] ← false; // S 초기화

       Dist[i] ← weight[v, i]; // Dist 초기화

}

S[v] ← true;

Dist[v] ← 0;

for(i←0; i<n-2; i←i+1) do { // n-2번 반복

  select u such that // 새로운 최단 경로를 선정

        Dist[u] = min{Dist[j] | S[j] = false and 0<= j < n};

S[u] ← true;

for(w←0; w<n; w←w+1) do { // 확정이 안된 경로들에 대해 다시 계산

   if(S[w] = false) then {

            if(Dist[w] > (Dist[u] + weight[u, w])

                   then Dist[w] ← Dist[u] + weight[u, w];

   }

}

}

알고리즘은 집합 S에 4개의 정점이 들어간 후 Dist계산을 마치고 모든 수행을 종료한다.

왜냐하면, 정점을 선정할 때 다음 최단 경로에 대한 거리를 다시 계산하기 때문에 마지막에 남은 하나의 정점은 자연히 최단 거리가 된다.



http://blog.naver.com/pajuri?Redirect=Log&logNo=120004529482