Algorithm - Floyd Warshall(플로이드 와샬)

Floyd-Warshall Algorithm :

모든 최단 경로를 구하는 알고리즘.

변의 가중치가 음이거나 양인 (음수 사이클은 없는) 가중 그래프에서 최단 경로들을 찾는 알고리즘. 알고리즘을 한 번 수행하면 모든 꼭짓점 쌍 간의 최단 경로의 길이(가중치의 합)를 찾음. 알고리즘 자체는 경로를 반환하지는 않지만, 알고리즘을 약간만 변형시키면 경로를 찾을 수 있음. 

'모든 정점'에서 '모든 정점'으로의 최단 경로를 구하고 싶다면 플로이드 와샬 알고리즘 사용. / 다익스트라 알고리즘은 가장 적은 비용을 하나씩 선택해야 했다면, 플로이드 와샬 알고리즘은 기본적으로 '거쳐가는 정점'을 기준으로 알고리즘을 수행한다는 특징이 있음. / Dynamic Programming 기술 사용. 

 

핵심 - 말그대로 거쳐가는 정점을 기준으로 최단거리 구하는 것

 

그래프에서 정점끼리의 최단 경로를 구하는 방법의 종류

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

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

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

- All pairs shortest path problem (모든 최단 경로를 구하는 문제)

 

Floyd Warshall 알고리즘은 위에서 네번째 경우에 해당함. 다익스트라 알고리즘이나 벨만 포드 알고리즘은 두 번째에 해당.

Floyd Warshall 은 다익스트라 와는 달리 음의 간선도 사용할 수 있음.

 

플로이드 와샬 알고리즘의 과정 :

모든 노드간의 최단거리를 구해야 하므로 2차원 인접 행렬을 구성함. 알고리즘은 여러 라운드로 구성. 라운드마다 각 경로에서 새로운 중간 노드로 사용할 수 있는 노드를 선택하고, 더 짧은 길이를 선택하여 줄이는 과정을 반복.

 

 

 

플로이드 와샬 알고리즘은 시간 복잡도가 O(n^3)으로, 그래프의 크기가 작아 세제곱 시간 알고리즘을 적용해도 문제가 풀릴 때만 사용 가능.

 

소스코드 구현 :

#include <stdio.h>

int number = 4;
int INF = 10000000;

int a[4][4] = { // 자료 배열 초기화
	{0, 5, INF, 8},
    {7, 0, 9, INF),
    {2, INF, 0, 4},
    {INF, INF, 3, 0}
};

void floydWarshall() {
	int d[number][number]; // 결과 그래프 초기화
    
    for (int i = 0; i < number; i++) 
    	for (int j = 0; j < number; j++) 
        	d[i][j] = a[i][j];

	for (int k = 0; k < number; k++) // k = 거쳐가는 노드
    	for (int i = 0; i < number; i++) // i = 출발 노드
        	for (int j = 0; j < number; j++) // j = 도착 노드
                if (d[i][k] + d[k][j] < d[i][j])
                    d[i][j] = d[i][k] + d[k][j];
                    
    for (int i = 0; i < number; i++) 
    	for (int j = 0; j < number; j++)
        	printf("%3d ", d[i][j]);
        printf("\n");
}

int main(void) {
	floydWarshall();
}