Path Algorithm Comparison

구분

• 단일 출발점에 대한 최단경로 문제

• 그래프에 음의 값이 포함된 경우
  Bellman-Ford

• 아닌 경우
  Dijkstra

• 전체 노드에 대한 최단경로 문제

• Floyd Warshall

• 그리고 Minimum Spanning Tree는 아래와 같다. 

• Kruskal

• Prim

알고리즘의 유사성

• Floyd-Warshall, Bellman-Ford, Dijkstra는 최단 경로를 구하는 알고리즘으로서 중간 경로가 선택되면 이를 거쳐가는 값과 그러하지 않은 경우를 비교하여 갱신한다는 점에서 모두 유사하다. 이러한 특성으로 인해 Dynamic Programming으로 문제를 해결하는데 왜 그런지는 Floyd-Warshall 항목에 설명이 되어 있다. 그런데 엄밀히 말하자면 Floyd-Warshall과 Bellman-Ford만 DP로 분류되고 Dijkstra는 Greedy 알고리즘으로 분류된다. 이는 Dijkstra가 경유지를 선택할 때 기존 노드들과 가장 짧은 거리의 노드를 선택하기 때문이다. 
• Floyd-Warshall이 모든 source로부터 모든 destination을 다루고 있고 Dijkstra와 Bellman-Ford는 one source – all destination이다. 그러니까 Floyd-Warshall에서는 경유지/시작점/도착지의 세 루프로 구성되고 Dijkstra와 Bellman-Ford는 경유지/목적지의 두 루프만 있다.
• 또 비교할만한 다른 특성이 있는데 Floyd-Warshall과 Dijkstra는 vertex 중심이라 vertex들을 순회한다. 그래서 time complexity도 각각 O(V³)와 O(V²)인데 반해 Bellman-Ford는 edge 중심으로 destination vertex의 거리 값을 갱신하기 때문에 O(VE)이라는 점이 다르다.
• Dijkstra와 Prim은 Greedy 알고리즘인데 해에 포함된 set과 포함되지 않는 set을 정해놓고 옮겨가는 과정에서 가장 작은 값을 pick한다는 점에서 유사하다. 코드도 거의 같은데 Dijkstra를 root를 고정한 MST라고 볼 수 있다.
• Prim과 Kruskal은 MST (Minimum Spanning Tree)를 만드는 알고리즘이라는 점에서 비슷하고 Greedy 알고리즘이라는 점에서도 비슷하다. 
• 그렇다면 Prim과 Kruskal의 차이점을 보자. Prim은 처음부터 MST set을 유지하고 그 set에서 가장 가까운 vertex를 greedy하게 선택하여 MST set을 전체로 확장해 나가는 방법이다. 이와 달리 Kruskal은 cycle을 이루지 않는 가장 작은 edge들을 차례로 선택함으로써 최종 단계에서 결국 MST가 되는 방법이다. 사용하는 알고리즘도 Prim은 set에서 최소 거리의 vertex를 찾기 위해 PriorityQueue, 그러니까 heap을 사용하고, Kruskal은 edge를 정렬하기 위한 sorting과 cycle여부를 판단하기 위해 union-find를 사용한다.

Floyd-Warshall

• 가장 외우기 쉽다.
• 출발지점 i에서부터 도착지점 j로의 최단 경로의 값을 구한다. 따라서 결과 값은 dist[출발지][도착지]와 같이 2차원 array에 담긴다.

모든 중간 경로 k를 다 고려하여 { 모든 시작점에서 대해 { 모든 도착지점을 계산 한다 { 방문지 k를 거쳐가는 것이 기존 값보다 짧다면 그것으로 거리를 갱신한다. } } }

• 따라서 가장 핵심되는 코드는 

// 기존 방법보다 i에서 k를 경유하여 j로 가는 방법이 // 더 짧다면 그 값으로 갱신한다. if (dist[i][k] + dist[k][j] < dist[i][j]){     dist[i][j] = dist[i][k] + dist[k][j];  }

• 이를 k, i, j에 대해 3중 for문을 돌면된다. (루프 순서가 경유지/시작점/도착점 이라는 것은 외워야한다)

void floyd(int graph[][V]){
    int dist[V][V];
  
    // Initialize distances
    for (int i = 0; i < V; i++)
        for (int j = 0; j < V; j++)
            dist[i][j] = graph[i][j];
 
    // Update distances
    for (int k = 0; k < V; k++)
        for (int i = 0; i < V; i++)
            for (int j = 0; j < V; j++)
                if (dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
 
    printSolution(dist);
} 

Bellman-Ford

• Floyd-Warshall에서 시작점을 0으로 고정한 것이라고 보면 된다. 그렇다면 시작점 루프를 제거하고 경유지 루프와 도착지 루프만 남기면 될 것이다. 하지만 그걸 Bellman-Ford라고 하진 않는다. 
• Bellman-Ford는 Floyd-Warshall과 또 다른 특성이 있는데 edge 중심으로 스캔을 한다는 점이다. 즉, 모든 목적지에 대해 특정 edge를 거치는지 거치지 않는지를 판단한다. 

Vertex – 1 만큼 아래의 경우를 반복 { 모든 edge에대해 { 모든 edge의 destination에 대해 해당 edge를 거쳤을 때 기존 값보다 작다면 그 값으로 갱신한다. } }

• 여기서 좀 특이한 것은 바깥 루프에서 안쪽 계산식에 영향을 미치는 변수가 없다는 것이다. 그냥 안쪽 루프를 일정 횟수만큼 반복하게 하는 역할만 한다. 
• 그런데 왜 하필 vertex개수 - 1만큼 반복하는가? 그것은 모든 노드까지의 최소 경로는 아무리 많아도 vertex 개수보다 하나 작기 때문이다.
• 가장 핵심되는 코드는 아래와 같다. 여기서 dist[u]는 출발지에서 u까지 가는 거리이다. u는 선택된 edge의 source이고 v는 destination이다. 만일 지금까지 알고 있던 dist[v]보다 dist[u] + weight (edge의 값 = u-v사이의 거리)가 더 작다면 지금까지 알고 있던 dist[v]는 더 작은 값으로 갱신된다. 

// 지금까지 알고 있던 v까지의 거리 dist[v]보다 u를 거쳐가는 경로, 즉 dist[u] + weight가 더 작다면 dist[v]는 갱신된다. if (dist[u] != MAX_INT && dist[u] + weight < dist[v])    dist[v] = dist[u] + weight;

• 이를 앞서 말한 바와 같이 모든 edge에 대해서 수행하고 (vertex 개수 – 1)만큼 반복하면 아래의 코드가 된다. 첫번째 순회에서는 edge 하나를 거쳐갈 수 있는 거리들이 갱신되고, 두번째 순회에서는 최대 edge 두개를 거쳐갈 수 있는 거리들로 갱신된다. 

void bellmanford(Edge edge[], int src)
{
    int dist[V];
 
    // Initialize distances from src to all other vertices as INFINITE
    for (int i = 1; i < V; i++)
        dist[i] = MAX_INT;
    dist[0] = 0;
  
    // Update distance considering all edges
    for (int i = 1; i <= V - 1; i++) {
        for (int j = 0; j < E; j++) {
            int u = graph->edge[j].src;
            int v = graph->edge[j].dst;
            int weight = graph->edge[j].weight;
            if (dist[u] != MAX_INT && dist[u] + weight < dist[v])
                dist[v] = dist[u] + weight;
        }
    }
 
    printSolution(dist);
} 

Dijkstra

• 기본 틀은 아래의 로직을 반복하는 것이다. 

모든 방문하지 않은 vertex들에 대해 { 1) 시작점에서 가장 가까운 vertex를 하나 선택한다. 2) 이것을 방문지 (SPT, Shortest Path Tree) set에 집어넣는다. 3) 그러면서 방문하지 않은 다른 모든 vertex들의 거리를 갱신한다. 선택된 vertex를 거쳐가면 더 빠른지를. }

• 가장 핵심되는 코드는 아래와 같다. 

// 시작점에서 가장 가까운 u를 sptSet에 포함시킨다 int u = ... // min distance in sptSet sptSet[u] = true; if (!sptSet[v] // 방문하지 않았던 모든 vertex에 대해서         && graph[u][v]  // u와 직접적인 경로가 있다면         // u까지의 거리에 u-v간 거리를 더한 값이 기존 v까지의 거리보다 작다면         && (dist[u] != INT_MAX)         && (dist[u] + graph[u][v] < dist[v]))      // (출발지에서부터) v까지의 거리를 갱신한다.     dist[v] = dist[u] + graph[u][v];

• 이를 앞서 말한 바와 같이 모든 vertex들이 sptSet에 뽑힐 때까지 수행하고 선택된 vertex에 대해 다른 모든 vertex들에 대한 비교&갱신을 하면 아래의 코드가 된다. 

void dijkstra(int graph[V][V], int src)
{
    int dist[V]; 
    bool sptSet[V];
 
    // Initialize distances
    for (int i = 0; i < V; i++)
        dist[i] = INT_MAX, sptSet[i] = false;
    dist[src] = 0;
 
    // Find shortest path for all vertices
    for (int count = 0; count < V-1; count++)
    {
        int u = minDistance(dist, sptSet); // pick minimum distance
        sptSet[u] = true;
 
        for (int v = 0; v < V; 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];
    }
 
    printSolution(dist);
} 

Prim

• Dijkstra와 코드가 거의 유사한데, 기본 틀은 아래의 로직을 반복하는 것이다. 

아직 MST에 포함되지 않은 vertex들에 대해 { 1) key값이 가장 작은 vertex를 하나 선택한다. (그것을 u라 부른다). 2) 이것을 MST set에 집어넣는다. 3) 그러면서 u의 이웃노드들의 기존 key 값보다 u-v edge weight가 작다면update한다. }

• 따라서 가장 핵심되는 코드는 아래와 같다. 

// u를 MST에 포함시킨 다음 모든 v에 대해서 아래의 조건 체크 if (graph[u][v] // u와 직접적인 경로가 있고           // 아직 MST set에 포함되어 있지 않으며         && (mstSet[v] == false)         // u-v간 거리가 기존 key값 보다 작다면         && (graph[u][v] < key[v]))     // v의 source거리를 갱신한다.     parent[v] = u, key[v] = graph[u][v];

• 이를 앞서 말한 바와 같이 모든 vertex들이 MST에 뽑힐 때까지 수행하고 선택된 vertex에 대해 다른 모든 vertex들에 대한 비교&갱신을 하면 아래의 코드가 된다. 

void primMST(int graph[V][V])
{
    int parent[V];
    int key[V];
    bool mstSet[V];
 
    for (int i = 0; i < V; i++)
        key[i] = INT_MAX, mstSet[i] = false;
 
    // include 1st vertex in MST
    key[0] = 0;
    parent[0] = -1;
 
    for (int count = 0; count < V-1; count++)
    {
        int u = minKey(key, mstSet);
        mstSet[u] = true;
 
        for (int v = 0; v < V; v++)
            if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])
                parent[v] = u, key[v] = graph[u][v];
    }
 
    printMST(parent, V, graph);
}

Kruskal

• Greedy 방식으로 MST를 구한다는 점에서 Prim과 유사하다. 차이점은 vertex를 스캔하여 MST와 가장 가까운 것을 선택하는 Prim의 방법과 달리 Kruskal에서는 edge를 스캔한다는 점이다. Kruskal에서는 edge를 정렬한 뒤 작은 것부터 선택하고 그것이 cycle을 이루지 않으면 채택한다. (MST의 edge개수는 vertex개수 보다 하나 작기 때문에 V – 1개 선택하면 된다)
• 따라서 가장 핵심되는 코드는 아래와 같다. 

// edge들을 정렬한다. qsort(graph->edge); // 결과 배열에 edge가 V – 1개 선택될 때까지 반복한다. while (e < V - 1) {     // 정렬된 edge 배열에서 가장 작은 edge를 선택한다.     Edge smallestEdge = graph->edge[i++];     // edge를 MST에 포함시키면 cycle을 이루는지 확인한다.     if (isCycle(smallestEdge.src, smallestEdge.dst) == 0) {         // cycle을 이루지 않으면 결과 배열에 넣는다.         result[e++] = smallestEdge;     } }

• 실제로 cycle여부는 Union-Find알고리즘을 사용한다. Edge의 양쪽 vertex가 같은 subset에 속하는지로 cycle여부를 알수 있고 cycle이 아니라면 edge를 선택한 뒤 양쪽 vertex를 같은 subset에 속하도록 만든다.

void kruskalMST(Graph* graph)
{
    int V = graph->V;
    Edge* result = (Edge*)malloc(V * sizeof(Edge));
 
    qsort(graph->edge, graph->E, sizeof(graph->edge[0]), myComp);
 
    Subset* subsets = (Subset*)malloc(V * sizeof(Subset));
    for (int v = 0; v < V; ++v) {
        subsets[v].parent = v;
        subsets[v].rank = 0;
    }
 
    int i = 0, e = 0;
    while (e < V - 1) {
        Edge smallestEdge = graph->edge[i++];
        int x = findRoot(subsets, smallestEdge.src);
        int y = findRoot(subsets, smallestEdge.dst);
 
        // if including this edge does't cause cycle, include it in result
        if (x != y) {
            result[e++] = smallestEdge;
            doUnion(subsets, x, y);
        }
    }
 
    printMST(result, e);
}