플로이드-와샬 알고리즘(C++)

플로이드-와샬을 사용 해야 할 경우!

---

플로이드-와샬 알고리즘은 "모든 정점 쌍에 대해 최단 거리를 구할 떄 " 사용한다.

즉, 모든 정점의 최단거리를 구하고 싶을 떄 다익스트라나 밸만-포드가 아닌 플로이드-와샬 알고리즘을

사용하면 된다.

 

플로이드 알고리즘은 그래프의 모든 정점 쌍의 최단 거리를 저장하는 2차원 배열 map[][]을 계산한다.

map[u][v]의 의미는 정점 u에서 정점 v로 가는 최단거리를 나타낸다.

 

플로이드 알고리즘의 경로와 경유점의 개념

---

두 정점 u와 v를 이어주는 경로가 있을 때, 이 경로는 항상 u와 v를 지난다.

이 외에도 다른 정점을 거칠 수 있다.

 

 

 

정점 u에서 정점 v로 가는 최단 경로를 D(u,v)라고 하자.

정점 a에서 정점 b로 갈때 5만큼의 비용이 드는데, c,d를 거쳐서 간다면 4의 비용이 든다.

 

(즉 경우에 따라서 정점 u에서 정점 v를 바로 가는 것이 최소가 아닌 다른 정점을 거칠 떄 최소가 될수 있다.)

정점들 중 하나를 골라서 이를 x라고 할때 정점 u에서 정점 v로 가는 최단 경로는

 

x를 거칠 수도 있고, x를 건너뛸 수도 있다.

 

1) X를 거칠 경우

이 경우에는 u에서 x로 가는 경로와 x에서 v로 가는 경로를 더하면 최종적인 경로가 나온다.

위에서  a->b로 가는 경로일때, c,d를 거치는데 이는 a->c + c->d + d->b의 형태가 된다.

 

2) X를 거치지 않을 경우

정점 u에서 정점 v로 바로 가기 떄문에 이 경우는 a->b의 형태가 된다.

 

이를(정점과 정점의 최단 경로) 점화식 형태로 구해본다면

D(u,v) = min(D(u,v), D(u,x) + D(x,v)) 의 값이 나온다.

 

다만, 인접 행렬에서 간선이 없는 경우 매우 큰 값을 넣어준다. (경로가 없는 경우)

또한 인접행렬에서 행과 열의 번호가 같은경우에는, 즉 D(u,u)일 경우에는 0을 넣어준다.

(자기자신에서 자기자신으로 가는 최단경로는 0이기 떄문에)

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int map[101][101]; //인접 행렬 형식
int n;
const int MAX = 987654321; //경로가 없을 경우 매우 큰 값
int min(int a,int b){
    if(a>b){
        return b;
    }
    else{
        return a;
    }
}
void floyd(){ //시간복잡도 O(n^3)
    for(int k = 0;k<n;k++){
        for(int i = 0;i<n;i++){
            for(int j = 0;j<n;j++){
            	//i에서 j로 가는 최단 경로
                //min((i,j),(i,k)+(k,j))
                
                map[i][j] = min(map[i][k] + map[k][j],map[i][j]);
            }
        }
    }
}
 
void input(){
    cin >> n;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            cin >> map[i][j];
        }
    }
 
}
 
void init(){
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            if(map[i][j] == 0){
                map[i][j] = MAX;
            }
        }
    }
}
int main(void){
    input();
    init();
    floyd();
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            if(map[i][j] == MAX){
                map[i][j] = 0;
            }
            else{
                map[i][j] = 1;
            }
            cout << map[i][j] << ' ';
        }
        cout << '\n';
    }
}