Dijkstra Algorithm

Shortest Path - Dijkstra Algorithm

• 방향그래프(Directed Graph)의 간선이 양수의 Weight를 가질 때 임의의 출발 정점에서 도착 정점까지의 경로 중 경로의 길이가 최소인 경로를 최단경로라고 정의한다.
• 이러한 최단경로는 도로망, 항공로 지도, 작업공정계산 등에 널리 응용된다. 최단경로는 다익스트라의 알고리즘으로 구할 수 있다.

다익스트라의 알고리즘

1. 인접행렬 상태로 각 간선의 가중치(Weight)가 존재하도록 한다.
   정점 i에서 i까지의 가중치는 0이고 정점 i에서 j까지의 간선 E(i, j)가 존재치 않으면 가중치는 무한대(∞)가 된다.
2. 집합 S와 T를 정하는데 S는 출발 정점을 초기값으로 하고 집합 T는 출발 정점을 제외한 모든 정점을 포함하도록 초기화한다.
3. 출발 정점을 제외한 모든 정점으로부터의 거리의 초기값(dist[i], 2<=i<=n)을 [1]의 인접행렬에서 취한다.
4. 집합 T의 원소 중 출발점으로부터의 거리가 최소인 정점 v를 택하여 T에서 제거하고 집합 S에 추가한다.
5. T집합내의 모든 정점 w에 대해 출발점으로부터의 거리(dist[w])와 간선 E(v, w)의 길이에 v정점의 거리(dist[v])를 합한 값 중 작은 것을 선택하여 정점 w의 거리(disw[w])로 한다.
6. [4]와 [5]의 과정을 T집합이 공집합이 될 때까지 반복한다.

shortest(int adj_matrix[n][n]) {
    T={2, 3, ..., n};
    S={1};

    for(i=2; i<=n; i++)
        dist[i]=adj_matrix[1][i];        //초기 경로 길이
    for(i=2; i<=n; i++) {
        v=T내의 정점 중 dist[i]가 최소인 정점;
        T에서 v를 삭제;
        S에서 v를 삽입;
        while(T내의 모든 정점 w에 대해)
            dist[w]=MIN(dist[w], dist[v]+adj_matrix[v][w])
    }
    return(dist
}

adj+matrix[ ][ ]는 각 간선의 인접행렬:

초기 상태
S = {0}
T = {1, 2, 3, 4, 5, 6}

• 위의 초기상태는 정점 0에서 다른 모든 정점까지의 거리를 보여준다.
• 초기상태에서 dist[]값 중에서 가장 작은 값을 가진 정점 4를 선택하여 집합 S에 삽입하고 집합 T에서 삭제한다.
• 정점 0에서 모든 정점까지의 거리와 정점 0에서 정점 4를 거쳐서 모든 정점까지 가는 거리를 비교하여 작은 값을 선택한다.
• 아래의 그림에서 정점 2까지의 거리가 9에서 7로 변화된 것을 볼 수 있다. 이와 같이, 집합 T에 있는 모든 정점에 대해 동일한 과정을 반복하고 그 결과를 반영한다.

S = {0, 4}
T = {1, 2, 3, 5, 6}

dist[1]:
11 < dist[4] + adj_matrix[4][1] = 3+∞ = ∞

dist[2]:
9 > dist[4] + adj_matrix[4][2] = 3+4 = 7

dist[3]:
∞ > dist[4] + adj_matrix[4][3] = 3 + 16 = 19

dist[5]:
∞ > dist[4] + adj_matrix[4][5] = 3 + 21 = 24

dist[6]:
∞ > dist[4] + adj_matrix[4][6] = 3 + 40 = 43

S = {0, 2, 4}
T = {1, 3, 5, 6}

dist[1]:
11 < dist[2] + adj_matrix[2][1] = 7 + ∞ = ∞

dist[3]:
19 < dist[2] + adj_matrix[2][3] = 7 + ∞ = ∞

dist[5]:
24 > dist[2] + adj_matrix[2][5] = 7 + 12 = 19

dist[6]:
43 < dist[2] + adj_matrix[2][6] = 7 + ∞ = ∞

S = {0, 1, 2, 4}
T = {3, 5, 6}

dist[3]:
19 < dist[1] + adj_matrix[1][3] = 11 + ∞ = ∞

dist[5]:
19 < dist[1] + adj_matrix[1][5] = 11 + ∞ = ∞

dist[6]:
43 > dist[1] + adj_matrix[1][6] = 11 + 30 = 41

S = {0, 1, 2, 3, 4}
T = {5, 6}

dist[5]:
19 < dist[3] + adj_matrix[3][5] = 19 + ∞ = ∞

dist[6]:
41 > dist[3] + adj_matrix[3][6] = 19 + 21 = 40

S = {0, 1, 2, 3, 4, 5}
T = {6}

dist[6]:
40 > dist[3] + adj_matrix[5][6] = 19 + 18 = 37

• 최종적으로 집합 T에 모든 정점이 제거되었을 때 dist[]에 남아있는 값들이 정점 0에서 다른 모든 정점까지의 최단거리를 나타내는 값이 된다. 최종적인 최단경로는 위에서 보는 바와 같다.

예)
시작정점 0에서 3까지는 19
시작정점 0에서 6까지는 37