플로이드 와샬(Floyd Warshall)

개념

---

플로이드 와샬은 모든 정점과 정점의 최단 경로를 탐색하는 알고리즘이다 

거쳐가는 정점을 기준으로 최단 경로를 계산한다 

 

 주의: 플로이드 알고리즘은 음수 가중치가 없는 무조건 양수의 그래프에서 동작합니다

코드

---

#include <iostream>

#define MAX 101
#define MIN(a,b) a<b ? a:b
#define INF 1000

using namespace std;

int N, M;
int map[MAX][MAX];

// 맵 초기화
void initMap(){
    for(int i = 0; i <= N; i++){
        for(int j = 0; j <= N; j++){
            map[i][j] = INF;
            if(i == j) map[i][j] = 0;
        }
    }
}

// 모든 정점과 정점의 최단 거리를 구함
void floyd(){
    for(int k = 0; k <= N; k++){
        for(int i = 0; i <= N; i++){
            for(int j = 0; j <= N; j++){
                map[i][j] = MIN(map[i][j], map[i][k] + map[k][j]);
            }
        }
    }
}

int main(){
    cin >> N >> M;

    initMap();

	// 입력
    for(int i = 0; i < M; i++){
        int a, b;
        cin >> a >> b;

        map[a][b] = map[b][a] = 1;
    }
    
    floyd();

	// 출력
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            printf("%d ", map[i][j]);
        }
		printf("\n");
    }

    return 0;
}

풀이

---

1. 초기화

우선 최단경로를 적을 map[][]을 INF로 초기화 시킵니다 

 

2. 점화식

플로이드 알고리즘의 핵심은 i에서 j의 최단 경로를 구하는 점화식입니다 

map[i][j] = MIN(map[i][j], map[i][k] + map[k][j]);

정점i에서 정점j로 바로 가는 경로와, 정점k를 지나서 가는 경로 중 최소값을 구해서 넣어줍니다