최단거리구하기_플로이드 와샬(Floyd Warshall) 알고리즘

플로이드 알고리즘에 대한 이해

- 플로이드 알고리즘이란, 그래프의 모든 정점 쌍 사이의 최단 거리를 구하는 알고리즘이다.

- 모든 정점 쌍에 대한 2차원 표를 채우는 과정으로 진행된다.

 

 

V(노드의 개수) = 6, E(간선의 개수) = 7 인 다음과 같은 그래프에서 모든 정점 쌍 사이의 최단 거리를 구해보자.

먼저, 아무 정점도 거치지 않았을 때 정점 i와 정점 j 사이의 최단 거리로 표를 채운다.

 

 

 

 

예를 들어, 정점 3과 정점 6은 아무 정점도 거치지 않았을 때 거리가 8이다. 물론, 3 -> 2 -> 5 -> 6 으로 이동하는 경우 더 작은 거리(7)로 도달할 수 있으나, 가장 처음에는 다른 정점을 거치는 경우를 제외하고 직행으로 연결하였을 때의 최단 거리만 표에 기록한다. 

 

 

int V, E;
vector<vector<int>> dist(105, vector<int>(105, INF));

void getInput() {

    cin >> V >> E;
    
    // 자기 자신의 노드에서 자신의 노드까지의 최단 거리는 항상 0
    for (int i=1; i<=V; i++) dist[i][i] = 0;
    
    // 간선과 거리를 입력받아 아무 정점도 거치지 않았을 때의 최단 거리 갱신
    while (E--) {
        int u, v, c;
        cin >> u >> v >> c;
        dist[u][v] = min(dist[u][v], c);
        dist[v][u] = min(dist[v][u], c);
    }
}

 

 

이후, 다른 노드를 거쳤을 때의 거리와 비교하여 최단 거리를 갱신해 나간다. 

만약, 정점 i에서 정점 j까지 이동 할 때, 정점 k를 거쳐가는 것이 더 거리가 짧다면(dist[i][j] > dist[i][k]+dist[k][j]) 정점 i에서 정점 j까지의 최단 거리를 k를 거쳐 이동하는 거리로 갱신해주면 된다. 

 

 

void Floyd() {
	
    // 정점 k를 지나갔을 때 거리가 더 줄어드는 지 확인 후 갱신
    for (int k=1; k<=V; k++) {
        for (int i=1; i<=V; i++) {
            for (int j=1; j<=V; j++) 
                dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
        }
    }
}

 

 

경로 추적

 정점 i에서 정점 j까지 최단거리로 이동할 때의 경로를 알기 위해서, 별도의 2차원 배열 nxt를 선언한다. nxt[i][j]는 정점 i에서 정점 j까지 최단거리로 이동할 때 가장 먼저 방문해야 하는 정점이다. 

 

처음 간선의 정보를 입력 받을 때, 정점 i와 j가 직행으로 연결되어있다면, nxt[i][j] = j 가 된다. 

이후, dist[i][j]의 값이 갱신 될 때, 정점 i에서 정점 j로 이동하는 과정에서 먼저 정점 k를 방문해야 한다면, nxt[i][j] = nxt[i][k]가 된다.

 

재귀 함수와 nxt에 기록된 정보를 통해 경로를 추적하면 된다.

 

 

플로이드 알고리즘의 시간복잡도

플로이드 알고리즘의 시간복잡도는 O(V^3)이다.

 

 

전체 코드

#include <vector>
#include <iostream>

using namespace std;
#define INF 1000000000

int V, E, s, e;
vector<vector<int>> dist(105, vector<int>(105, INF));
vector<vector<int>> nxt(105, vector<int>(105, 0));


void getInput() {

    cin >> V >> E;
    
    // 자기 자신의 노드에서 자신의 노드까지의 최단 거리는 항상 0
    for (int i=1; i<=V; i++) dist[i][i] = 0;
    
    // 간선과 거리를 입력받아 아무 정점도 거치지 않았을 때의 최단 거리 갱신
    while (E--) {
        int u, v, c;
        cin >> u >> v >> c;
        dist[u][v] = min(dist[u][v], c);
        dist[v][u] = min(dist[v][u], c);
        nxt[u][v] = v; // 정점 u에서 v로 직행할 때 가장 먼저 방문해야 하는 정점 v
        nxt[v][u] = u; // 정점 v에서 u로 직행할 때 가장 먼저 방문해야 하는 정점 u
    }
}


void Floyd() {
	
    // 정점 k를 지나갔을 때 거리가 더 줄어드는 지 확인 후 갱신
    for (int k=1; k<=V; k++) {
        for (int i=1; i<=V; i++) {
            for (int j=1; j<=V; j++) 
                if (dist[i][j] > dist[i][k]+dist[k][j]) {
                    dist[i][j] = dist[i][k]+dist[k][j];
                    nxt[i][j] = nxt[i][k];
                }
        }
    }
}


// 모든 정점 쌍에 대한 최단 거리 출력
void printDist() {

    for (int i=1; i<=V; i++) {
        for (int j=1; j<=V; j++)
            cout<<dist[i][j]<<" ";
        cout<<endl;
    }
}


// 정점 s에서 정점 e까지의 최단 경로 복원
void findRoute(int s, int e, vector<int>& v) {

    v.push_back(s);
    if (nxt[s][e] == e) {
        v.push_back(e);
        return ;
    }
    findRoute(nxt[s][e], e, v);
}


int main() {

    getInput();
    Floyd();
    
    //최단 거리 출력
    printDist();

    // 정점 s와 e의 최단 거리 경로 복원
    // cin >> s >> e;
    // vector<int> re;
    // findRoute(s, e, re);
    // for (auto x : re) cout<<x<<" ";
    // return 0;
}


/*
input: 
6 7 
1 2 3
2 5 5
2 3 1
2 4 4
3 4 2
3 6 8
5 6 1

output: 
0 3 4 6 8 9 
3 0 1 3 5 6 
4 1 0 2 6 7 
6 3 2 0 8 9 
8 5 6 8 0 1 
9 6 7 9 1 0
*/