Dijkstra's Shortest Path

개요 

• One source to all destinations에 대한 shortest path 문제이다. (혹은 최소거리를 구하면 된다)
• 만일 all sources to all destinations라면 Floyd Warshall 방법을 사용하여야 한다.

방법

• Greedy방법으로 Prim의 MST 방법이랑 매우 유사하다. (Root를 고정한 MST라고 볼 수 있다) 
• 두 개의 set을 유지한다. 첫 째는 shortest path set, 두번 째는 여기에 포함되지 않은 녀석들의 set. 
• 그래서 알고리즘은 포함되지 않은 set에서 node 하나를 꺼내서 source에서 거기로 가는 최소거리를 구하면된다. 

1) sptSet (Shortest Path Tree Set)을 만든다. 여기에 포함되는 node (vertex)는 source로부터 최단 경로가 확정된 것들이다. 초기에는 당연히 empty set이다. 2) 입력 그래프의 모든 node (vertex)에 거리를 대입한다. 3) sptSet이 모든 vertex를 포함할 때까지 a) 포함되지 않는 node set에 있는 녀석들 중 최소 거리를 가진 녀석 u를 선택한다. b) u를 sptSet에 포함시킨다. c) u의 모든 이웃 노드들 (adjacent vertices)의 거리 값을 update한다.

예제

• 아래의 그래프를 예로 들어 보자.

• 최초에 sptSet은 empty이고 node들의 거리는 {0, INF, INF, INF, INF, INF, INF, INF}이다. 
• 여기서 최소 거리 노드를 pick하면 0 node가 선택된다. 따라서 sptSet은 {0}이 되고 노드들의 거리는 update된다. 이웃 노드들은 1과 7이고 거리는 4와 8이다. 이를 그림으로 나타내면 아래와 같다. sptSet에 포함된 경우 녹색이고 거리가 무한인 node들은 제외하였다. 

• 이번엔 node 1이 pick된다. sptSet은 이제 {0, 1}이되고 1의 이웃 노드들의 거리는 갱신된다. node 2의 거리가 12로 바뀌었다.

• 이번엔 node 7이 pick된다. sptSet = {0, 1, 7}, node 6과 8의 거리가 각각 9와 15로 바뀌었다.

• 이번엔 node 6가 pick된다. sptSet = {0, 1, 7, 6}, node 5와 8의 거리가 각각 11과 15로 바뀌었다. (8은 안바뀌지 않나?)

• 이 과정을 모든 node가 선택될 때까지 진행한다. 그럼 아래와 같은 Shortest Path Tree를 확보한다.

Code

#include <stdio.h>
#include <limits.h>
  
// Number of vertices in the graph
#define V 9
  
// A utility function to find the vertex with minimum distance value, from
// the set of vertices not yet included in shortest path tree
int minDistance(int dist[], bool sptSet[])
{
    // Initialize min value
    int min = INT_MAX, min_index;
  
    for (int v = 0; v < V; v++)
        if (sptSet[v] == false && dist[v] <= min)
            min = dist[v], min_index = v;
  
    return min_index;
}
  
int printSolution(int dist[], int n)
{
    printf("Vertex   Distance\n");
    for (int i = 0; i < V; i++)
        printf("%d \t %d\n", i, dist[i]);
}
  
// Funtion that implements Dijkstra's single source shortest path algorithm
// for a graph represented using adjacency matrix representation
void dijkstra(int graph[V][V], int src)
{
    int dist[V];     // The output array.  dist[i] will hold the shortest
                     // distance from src to i
 
    bool sptSet[V]; // sptSet[i] will true if vertex i is included in shortest
                    // path tree or shortest distance from src to i is finalized
 
    // Initialize all distances as INFINITE and stpSet[] as false
    for (int i = 0; i < V; i++)
        dist[i] = INT_MAX, sptSet[i] = false;
 
    // Distance of source vertex from itself is always 0
    dist[src] = 0;
 
    // Find shortest path for all vertices
    for (int count = 0; count < V-1; count++)
    {
        // Pick the minimum distance vertex from the set of vertices not
        // yet processed. u is always equal to src in first iteration.
        int u = minDistance(dist, sptSet);
 
        // Mark the picked vertex as processed
        sptSet[u] = true;
 
        // Update dist value of the adjacent vertices of the picked vertex.
        for (int v = 0; v < V; v++)
 
            // Update dist[v] only if is not in sptSet, there is an edge from 
            // u to v, and total weight of path from src to  v through u is 
            // smaller than current value of dist[v]
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX 
                                      && dist[u]+graph[u][v] < dist[v])
                dist[v] = dist[u] + graph[u][v];
    }
 
    // print the constructed distance array
    printSolution(dist, V);
}
  
// driver program to test above function
int main()
{
    /* Let us create the example graph discussed above */
    int graph[V][V] = {{0, 4, 0, 0, 0, 0, 0, 8, 0},
                       {4, 0, 8, 0, 0, 0, 0, 11, 0},
                       {0, 8, 0, 7, 0, 4, 0, 0, 2},
                       {0, 0, 7, 0, 9, 14, 0, 0, 0},
                       {0, 0, 0, 9, 0, 10, 0, 0, 0},
                       {0, 0, 4, 0, 10, 0, 2, 0, 0},
                       {0, 0, 0, 14, 0, 2, 0, 1, 6},
                       {8, 11, 0, 0, 0, 0, 1, 0, 7},
                       {0, 0, 2, 0, 0, 0, 6, 7, 0}
                      };
 
    dijkstra(graph, 0);
 
    return 0;
}

• 출력값이다. 

Vertex   Distance 0            0 1            4 2            12 3            19 4            21 5            11 6            9 7            8 8            14

• Time complexity는 O(n²)이다. 모든 노드에 대해서 다른 노드들의 distance를 모두 갱신한다. 
• Fibonacci heap을 사용하면 O(V logV)도 가능하다.