화투의 개발 블로그

앞서 다익스트라 알고리즘 포스트에서, 그래프에서 정점끼리의 최단 경로를 구하는 문제는 여러가지 방법이 있다고 했다.

하나의 정점에서 다른 하나의 정점까지의 최단 경로를 구하는 문제(single source and single destination shortest path problem)

하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제(single source shortest path problem)

하나의 목적지로가는 모든 최단 경로를 구하는 문제(single destination shortest path problem)

마지막으로 모든 최단 경로를 구하는 문제(All pairs shortest path problem).

플로이드-워셜 알고리즘은 이 중에서 마지막, 모든 최단 경로를 구하는 방법이다. (다익스트라는 single source shortest path problem였다.)

또한 다익스트라 알고리즘은 음의 가중치를 가진 간선은 못쓴다는 제약이 있었다. 하지만 플로이드-워셜에선 사용이 가능하다.

모든 정점에 대한 경로를 계산하므로 거리를 저장할 자료구조는 2차원 배열이 된다.

플로이드-워셜은 optimal substructure의 개념을 이용하여 최단 경로를 찾는다. optimal substructure란 특정 경로 안에 무수히 많은 경로가 있을 때, 중간 정점들이 각각 최단이 된다면 이를 모두 이은 경로 또한 최단이 된다는 개념이다.

1. 플로이드-워셜 알고리즘 기본 로직

플로이드-워셜에선 2개의 테이블을 사용하는데. 하나는 모든 경로에 대한 비용을 저장하는 테이블, 나머지 하나는 각 정점까지 가기 직전의 정점을 저장한 테이블이다. 각각의 테이블을 D와 P라고 하겠다.

테이블 D와 P에는 처음엔 인접 리스트에 대한 내용만 들어가게 된다. 그 후 경로를 추가 할 때마다 두 테이블이 갱신된다.

위 그래프를 보자. 플로이드-워셜에선 처음엔 인접리스트의 정보만 들어간다고 했다. 따라서 맨 처음에 초기화되는 테이블 D,P는 다음과 같다.

거리를 저장한 테이블 D

직전 정점을 저장한 테이블 P

여기서 INF는 무한대를 뜻하며, NIL은 직전 정점이 없다(즉 연결되어있지 않다)는 뜻이다. 위 정점은 아무런 정점을 중간 경로로 사용하지 않고, 오직 인접 리스트만 표현한 것이기 때문에, 그 외는 INF,NIL로 명시되었다.

이제 여기서 경로 1을 중간 경로로 하는 테이블을 구해보자. 얼핏 봐도 4->2가 중간경로 1을 추가하면 4->1->2로 접근 할 수 있고, 4->5도 4->1->5로 접근 할 수 있게 됨을 볼 수 있다.

중간 경로 1을 추가한 테이블 D

중간 경로 1을 추가한 테이블 P

이렇게 경로가 갱신되며, 갱신 될 시 테이블 P의 해당 컬럼 또한 1로 갱신된다. 직전 경로가 갱신되므로 테이블 P를 이용하면 최단 경로 또한 구할 수 있다. 

이를 모든 정점을 경로에 추가할 때 까지 반복한다.

따라서 다음과 같은 관계가 성립됨을 알 수 있다.

2. C++ 플로이드-워셜 알고리즘  코드

밑은 위 식과 개념으로 작성한 코드이다. 여기선 테이블을 두개로 안두고, pair로 그냥 하나의 테이블로 묶었다, 또한 테이블 P와 스택을 이용해서 경로 또한 구했다.

#include <iostream>
#include <vector>
#include <utility>
#include <stack>
#define MAX 987654321
#define NIL -1
using namespace std;
int n, m, x;
//플로이드 와샬 테이블. pair 하나는 D, 하나는 Pi 
vector<vector<pair<int, int> > > fw;
stack<int> path;
int main() {
    scanf("%d %d %d", &n, &m, &x);
    //플로이드 와샬 테이블 초기화. 
    fw.resize(n + 1);
    for (int i = 0; i<n; i++) {
        for (int j = 0; j<n; j++) {
            fw[i].push_back(make_pair(MAX, NIL));
            if (i == j) fw[i][j].first = 0;
        }
    }
    for (int i = 0; i<m; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        fw[u - 1][v - 1].first = w;
        fw[u - 1][v - 1].second = u - 1;
    }

    printf("///////////초기테이블///////////\n");
    printf("--거리\n");
    for (int i = 0; i<n; i++) {
        for (int j = 0; j<n; j++) {
            printf(fw[i][j].first == MAX ? "INF\t" : "%d\t", fw[i][j].first);
        }
        printf("\n");
    }
    printf("--직전 프로시져\n");
    for (int i = 0; i<n; i++) {
        for (int j = 0; j<n; j++) {
            printf(fw[i][j].second == NIL ? "NIL\t" : "%d\t", fw[i][j].second+1);
        }
        printf("\n");
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j<n; j++) {
            for (int k = 0; k<n; k++) {
                if (fw[k][j].first > fw[k][i].first + fw[i][j].first) {
                    fw[k][j].first = fw[k][i].first + fw[i][j].first;;
                    fw[k][j].second = fw[i][j].second;;
                }
            }
        }
    }

    printf("\n/////////완료 후 테이블/////////\n");
    printf("--거리\n");
    for (int i = 0; i<n; i++) {
        for (int j = 0; j<n; j++) {
            printf(fw[i][j].first == MAX ? "INF\t" : "%d\t", fw[i][j].first);
        }
        printf("\n");
    }
    printf("--직전 프로시져\n");
    for (int i = 0; i<n; i++) {
        for (int j = 0; j<n; j++) {
            printf(fw[i][j].second == NIL ? "NIL\t" : "%d\t", fw[i][j].second+1);
        }
        printf("\n");
    }
    printf("\n");
    for (int i = 0; i<n; i++) {
        for (int j = 0; j<n; j++) {
            if(fw[i][j].second == NIL) continue;
            printf("%d부터 %d까지 경로 : ",i+1,j+1);
            int pre = j;
            path.push(j+1);
            while (i != fw[i][pre].second) {
                pre = fw[i][pre].second;
                path.push(pre+1);
            }
            printf("%d",i+1);
            while(!path.empty()){
                printf("-%d",path.top()); path.pop();
            }
            printf("\n");
        }
    }

}

입출력 코드가 많아서 그렇지 플로이드-워셜 코드 자체는 되게 짧고 간결하다.

<실행 화면>

[문제 링크]

각 도시에서 한 도시로의 왕복 최단 거리 중에 최장 거리를 구하는 문제이다(?)

directed graph이기 때문에 X라는 도시에 갈 때와, X라는 도시에서 돌아 올 때의 경로는 둘 다 다르다.

난 이 문제를 3가지 방법으로 풀었다. 

.

1. 플로이드-와샬 알고리즘으로 전체 최단 경로를 구해 푸는 방법.

플로이드-와샬 알고리즘으로는 코드도 정말 간단하고,정답도 잘 나왔지만, 플로이드-와샬 자체가 O(n^3)인 알고리즘인지라 시간초과가 났다. 가지치기를 잘 하면 accept 되는거 같긴 한데, 그래도 다익스트라를 이용하는 것 보다는 느릴거란 생각이 들었다.(또 아무래도 정점의 갯수에 비헤 간선이 워낙 적기 때문이기도 한거같다.)

2. 다익스트라 알고리즘으로 X에서 출발하는 모든 최단 경로를 구한 뒤, 각 정점별로의 최단거리 또한 구해서 X까지 가는 방법.

모든 정점에 대해서 다익스트라 알고리즘을 사용해서 최대값을 구했다. 이건 accept가 뜨긴 떴다. 하지만 개인적으로 만족스럽지 않았다. 실행 속도도 속도지만, 굳이 각 정점에 대해서 최단 거리를 구할 필요가 있나 생각이 들었다. 

3. 다익스트라 알고리즘으로 X에서 출발하는 모든 최단 경로를 구한 뒤, 모든 간선을 뒤집어서 X에서 출발하는 정점을 구하는 방법.

일단 정방향으로 되어있는 인접리스트로 최단 경로를 구하고, 그다음 역방향으로 되어있는 인접리스트로 최단 경로를 구했다. 

그냥 간선만 방향을 바꿔주면 다른 모든 정점에서 X로 오는 정점을 구하는 것과 다를 게 없다. 따라서 2번과는 다르게 다익스트라 알고리즘을 단 2번만 사용해서 최대값을 구할 수 있다.

1. 플로이드-와샬 알고리즘으로 구현한 코드

#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#define MAX 987654321
using namespace std;
int n, m, x;
vector<vector<int> > fw;
int main() {
    scanf("%d %d %d", &n, &m, &x);
    fw.resize(n + 1);
    for (int i = 0; i<n; i++) {
        for (int j = 0; j<n; j++) {
            fw[i].push_back(MAX);
            if (i == j) fw[i][j] = 0;
        }
    }
    for (int i = 0; i<m; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        fw[u - 1][v - 1] = w;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j<n; j++) {
            for (int k = 0; k<n; k++) {
                if (fw[k][j] > fw[k][i] + fw[i][j])
                    fw[k][j] = fw[k][i] + fw[i][j];
            }
        }
    }
    int ret = 0;
    for (int i = 0; i<n; i++)
        ret = max(ret, fw[i][x] + fw[x][i]);
    printf("%d", ret);
}

2. 다익스트라 알고리즘 N번으로 구현한 코드

#include <cstdio>
#include <queue>
#include <vector>
#include <utility>
#include <algorithm>
#define MAX 987654321
using namespace std;
vector<vector<pair<int, int> > > adj;
int n, m, x;
typedef pair<int, int> node;
struct cmp {
    bool operator()(node x, node y) {
        return x.second > y.second;
    }
};
int ret[1001] = {0,};
void dijkstra(int x,int y) {
    priority_queue<node, vector<node>, cmp> pq;
    vector<int> dist(n+1,MAX); dist[x] = 0;
    pq.push(make_pair(x,0));
    for(int i=0; i<n;i++){
        if(i!=x) pq.push(make_pair(i,MAX));
    }
    while(!pq.empty()){
        int u = pq.top().first;
        int d = pq.top().second; pq.pop();
        if(d > dist[u]) continue;
        for(int i = 0; i<adj[u].size(); i++){
            int v = adj[u][i].first;
            int w = adj[u][i].second;
            if(dist[v] > dist[u] + w){
                dist[v] = dist[u] + w;
                pq.push(make_pair(v,dist[v]));
            }
        }       
    } 
    if(y==x){
        for(int i = 0; i<n; i++) ret[i] = dist[i];
    }
    else{
        ret[x] += dist[y];
    }    
}
int main() {
    scanf("%d %d %d", &n, &m, &x);
    adj.resize(n + 1);
    for (int i = 0; i<m; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        adj[u-1].push_back(make_pair(v-1, w));
    }
    dijkstra(x-1,x-1);
    for(int i=0; i<n; i++){
        if(i!=x)
            dijkstra(i,x);
    }
    int mv = 0;
    for(int i=0; i<n;i++) mv = max(mv,ret[i]);   
    printf("%d",mv);
}

3. 다익스트라 알고리즘 2번으로 구현한 코드

#include <cstdio>
#include <queue>
#include <vector>
#include <utility>
#include <algorithm>
#define MAX 987654321
using namespace std;
vector<vector<pair<int, int> > > adj1, adj2;
int n, m, x;
typedef pair<int, int> node;
struct cmp {
    bool operator()(node x, node y) {
        return x.second > y.second;
    }
};
int ret[1001] = {0,};
void dijkstra(int x, vector<vector<pair<int,int> > > adj) {
    priority_queue<node, vector<node>, cmp> pq;
    vector<int> dist(n+1,MAX); dist[x] = 0;
    pq.push(make_pair(x,0));
    for(int i=0; i<n;i++){
        if(i!=x) pq.push(make_pair(i,MAX));
    }
    while(!pq.empty()){
        int u = pq.top().first;
        int d = pq.top().second; pq.pop();
        if(d > dist[u]) continue;
        for(int i = 0; i<adj[u].size(); i++){
            int v = adj[u][i].first;
            int w = adj[u][i].second;
            if(dist[v] > dist[u] + w){
                dist[v] = dist[u] + w;
                pq.push(make_pair(v,dist[v]));
            }
        }       
    } 
    for(int i = 0; i<n; i++) ret[i] += dist[i];  
}
int main() {
    scanf("%d %d %d", &n, &m, &x);
    adj1.resize(n + 1);
    adj2.resize(n + 1);
    for (int i = 0; i<m; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        adj1[u-1].push_back(make_pair(v-1, w));
        adj2[v-1].push_back(make_pair(u-1, w));
    }
    dijkstra(x-1,adj1);
    dijkstra(x-1,adj2);
    int mv = 0;
    for(int i=0; i<n;i++) mv = max(mv,ret[i]);   
    printf("%d",mv);
}