#C++ #알고리즘 #자료구조

플로이드 와샬 알고리즘

플로이드 와샬 알고리즘에 대한 개념은 쉽게 많은 정보를 찾을 수 있으니 구현과 최단 거리가 아닌 최단 경로를 구하는 방법에 대해 알아보겠습니다.

플로이드 와샬 요약

하나의 정점에서 다른 모든 정점까지의 거리를 구하는 다익스트라 알고리즘과 달리 플로이드-워셜(Floyd Warshall) 알고리즘은 그래프 내의 모든 정점에서 모든 각 정점까지의 최단 거리를 구하는 알고리즘 입니다. 반복문 3개로 비교적 쉽게 구할 수 있으며 O(n^3)의 시간 복잡도를 갖습니다.

  1. k : 경유 정점
  2. i : 출발 정점
  3. j : 도착 정점

의 순서로 반복문 3개로 아래와 같이 i에서 출발해 정점 k를 경유하여 j 까지 가는 경우가 더 가깝다면 A를 더 가까운 정점으로 업데이트 합니다. 즉, 간단히 말해 아래와 같이 기존의 A[i][j] 와 A[i][k] + A[k][j] 중 더 작은 값이 A[i][j]의 값이 됩니다.

1
A[i][j] = min(A[i][k] + A[k][j], A[i][j])

최단경로 추적 구현

플로이드 와샬 알고리즘을 이용하면 최단 거리는 A배열에 저장되어 있어 A[i][j]의 형태로 정점 i부터 j까지의 최단 경로를 쉽게 구할 수 있습니다.

하지만 최단 거리가 아니라 최단 경로를 구하려면 경로를 따로 기록해두어야 합니다. 아래의 C++로 구현한 코드를 보면 최단 경로가 업데이트 될 때 마다 next 배열을 업데이트 하는 것을 볼 수 있습니다. next 배열은 현재 정점 i에서 도착 정점 j까지 가기위한 정점 i다음에 방문할 정점을 의미합니다. 따라서 next 배열에 A배열의 값이 업데이트 될때마다 기록을 해두어야 합니다.

예를 들어, next[5][3]은 정점 5에서 정점 3까지 가기 위해 정점 5 다음에 방문해야할 정점의 정점 번호를 의미합니다.

따라서 출발지에서 도착지까지 재귀함수를 이용해 출력하면 쉽게 최단 경로를 구할 수 있습니다. 경로 출력에 관한 함수는 trace_path()와 print_path()입니다.

쉽게 이해할 수 있도록 최대한 주석을 달아 두었으니 주석을 참고해주세요.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <bits/stdc++.h>

using namespace std;

using pii = pair<int, int>;

class Graph {
public:
    int n;
    // 인접 정점
    // first: 정점, second: 가중치
    vector<pii>* adj;

    Graph(int n) {
        this->n = n;
        adj = new vector<pii>[n];
    }

    // 간선 추가
    void insertEdge(int u, int v, int w) {
        this->adj[u].push_back(make_pair(v, w));
        this->adj[v].push_back(make_pair(u, w));
    }
};

// Floyd
vector<vector<int>>* floyd(Graph* g) {
    vector<vector<int>> A(g->n, vector<int>(g->n, INT_MAX));

    // next[i][j] : 정점 j까지 가기위한 정점 i다음에 방문할 정점
    vector<vector<int>>* next = new vector<vector<int>>(g->n, vector<int>(g->n));

    // 주어진 그래프의 초기 A와 next 행렬의 값 업데이트
    for (int i = 0; i < g->n; i++) {
        A[i][i] = 0; // 자신까지의 최단경로 = 0

        for (pii a : g->adj[i]) {
            A[i][a.first] = a.second;
            (*next)[i][a.first] = a.first;
        }
    }

    // i: 출발 노드, j: 도착 노드, k: 경유 노드
    for (int k = 0; k < g->n; k++) {
        for (int i = 0; i < g->n; i++) {
            for (int j = 0; j < g->n; j++) {
                // (i -> k) 나 (k -> j) 까지 도달할 수 없는 경우
                if (A[i][k] == INT_MAX || A[k][j] == INT_MAX) {
                    continue;
                }

                // k정점을 거쳐가는 경로가 더 가깝다면 업데이트
                if (A[i][k] + A[k][j] < A[i][j]) {
                    A[i][j] = A[i][k] + A[k][j];

                    // A가 업데이트 될때 next도 업데이트
                    (*next)[i][j] = (*next)[i][k];
                }
            }
        }
    }

    return next;
}

// 정점 u에서 v까지 갈때 다음번에 방문해야할 정점을 출력  
void trace_path(int u, int v, vector<vector<int>>* next) {
    // 출발지와 도착지가 같다면 멈춘다.  
    if (u != v) {
        // 정점 u 이후에 방문해야할 정점으로 u업데이트 후,  
        u = (*next)[u][v];
        cout << " -> " << u;
        // 재귀를 통해 반복  
        trace_path(u, v, next);
    }

}

// 시작정점도 출력해주기 위해 따로 분리  
void print_path(int u, int v, vector<vector<int>>* next) {
    cout << u;
    trace_path(u, v, next); //위의 함수를 이용해 경로 출력  
}

int main(void) {
    Graph* g = new Graph(7);
    g->insertEdge(0, 1, 7);
    g->insertEdge(1, 0, 7);
    g->insertEdge(0, 4, 3);
    g->insertEdge(4, 0, 3);
    g->insertEdge(0, 5, 10);
    g->insertEdge(5, 0, 10);
    g->insertEdge(1, 4, 2);
    g->insertEdge(4, 1, 2);
    g->insertEdge(1, 5, 6);
    g->insertEdge(5, 1, 6);
    g->insertEdge(1, 2, 4);
    g->insertEdge(2, 1, 4);
    g->insertEdge(1, 3, 10);
    g->insertEdge(3, 1, 10);
    g->insertEdge(2, 3, 2);
    g->insertEdge(3, 2, 2);
    g->insertEdge(4, 3, 11);
    g->insertEdge(3, 4, 11);
    g->insertEdge(4, 6, 5);
    g->insertEdge(6, 4, 5);
    g->insertEdge(6, 3, 4);
    g->insertEdge(3, 6, 4);
    g->insertEdge(3, 5, 9);
    g->insertEdge(5, 3, 9);

    // 최단 경로를 구한다.
    auto next = floyd(g);

    // 모든 정점부터 각 정점까지의 경로 출력
    for (int i = 0; i < g->n; i++) {
        for (int j = 0; j < g->n; j++) {
            cout << "["<< i << " -> " << j << "] : ";
            print_path(i, j, next);
            cout << "\n";
        }
        cout << "\n";
    }

    return 0;
}

실행 결과

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
[0 -> 0] : 0
[0 -> 1] : 0 -> 4 -> 1
[0 -> 2] : 0 -> 4 -> 1 -> 2
[0 -> 3] : 0 -> 4 -> 1 -> 2 -> 3
[0 -> 4] : 0 -> 4
[0 -> 5] : 0 -> 5
[0 -> 6] : 0 -> 4 -> 6

[1 -> 0] : 1 -> 4 -> 0
[1 -> 1] : 1
[1 -> 2] : 1 -> 2
[1 -> 3] : 1 -> 2 -> 3
[1 -> 4] : 1 -> 4
[1 -> 5] : 1 -> 5
[1 -> 6] : 1 -> 4 -> 6

[2 -> 0] : 2 -> 1 -> 4 -> 0
[2 -> 1] : 2 -> 1
[2 -> 2] : 2
[2 -> 3] : 2 -> 3
[2 -> 4] : 2 -> 1 -> 4
[2 -> 5] : 2 -> 1 -> 5
[2 -> 6] : 2 -> 3 -> 6

[3 -> 0] : 3 -> 2 -> 1 -> 4 -> 0
[3 -> 1] : 3 -> 2 -> 1
[3 -> 2] : 3 -> 2
[3 -> 3] : 3
[3 -> 4] : 3 -> 2 -> 1 -> 4
[3 -> 5] : 3 -> 5
[3 -> 6] : 3 -> 6

[4 -> 0] : 4 -> 0
[4 -> 1] : 4 -> 1
[4 -> 2] : 4 -> 1 -> 2
[4 -> 3] : 4 -> 1 -> 2 -> 3
[4 -> 4] : 4
[4 -> 5] : 4 -> 1 -> 5
[4 -> 6] : 4 -> 6

[5 -> 0] : 5 -> 0
[5 -> 1] : 5 -> 1
[5 -> 2] : 5 -> 1 -> 2
[5 -> 3] : 5 -> 3
[5 -> 4] : 5 -> 1 -> 4
[5 -> 5] : 5
[5 -> 6] : 5 -> 3 -> 6

[6 -> 0] : 6 -> 4 -> 0
[6 -> 1] : 6 -> 4 -> 1
[6 -> 2] : 6 -> 3 -> 2
[6 -> 3] : 6 -> 3
[6 -> 4] : 6 -> 4
[6 -> 5] : 6 -> 3 -> 5
[6 -> 6] : 6
#C++ #알고리즘 #자료구조


Follow @techbless