기술면접 알고리즘 [Graph] : Floyd-Warshall (플로이드 와샬 - 최단거리 쌍)

기술면접과 코딩테스트 준비를 위해 꼭 알아야 할 기초 알고리즘 관련 개념들과 코드를 정리하고 있습니다.

각 주제들은 GeeksForGeeks 의 Top 10 algorithms in Interview Questions 글에서 발췌하였습니다.

---

Floyd-Warshall (플로이드 와샬 - 최단거리 쌍)

플로이드 와샬(Floyd-Warshall) 알고리즘은 주어진 그래프의 모든 정점들에 대한 최소거리를 구하는 알고리즘이다. 원리는 매우 간단한데, 시작지점 i, 도착지점 j 의 거리 쌍을 중간 경유지 k 를 지나는 모든 경우에 대해 계속 relaxation 해주면 된다.

따라서 시간 복잡도는 (O^3) 이 나오게 된다.

#include <iostream>
#include <algorithm>

#define V 	4
#define INF	1000000

int min_val(int a, int b) {
	return a > b ? b : a;
}

void floydWarshall(int graph[V][V]) {

	std::cout << "Following matrix shows the shortest distances between every pair of vertices" << std::endl;	

	int res[V][V];
	//std::fill(&res[0][0], &res[V-1][V], INF);

	for (int i = 0; i < V; ++i)
		for (int j = 0; j < V; ++j)
			res[i][j] = graph[i][j];

	for (int k = 0; k < V; ++k) {
		for (int i = 0; i < V; ++i) {
			for (int j = 0; j < V; ++j) {
				res[i][j] = min_val(res[i][j], res[i][k]+res[k][j]);
			}
		}
	}

	for (int i = 0; i < V; ++i) {
		for (int j = 0; j < V; ++j) {
			if (res[i][j] == INF) {
				std::cout << "INF\t";
			} else std::cout << res[i][j] << "\t";

		}
		std::cout << std::endl;
	}

}


// Driver code
int main()
{
    /* Let us create the following weighted graph
            10
    (0)------->(3)
        |     /|\
    5 |     |
        |     | 1
    \|/     |
    (1)------->(2)
            3     */
    int graph[V][V] = { { 0, 5, INF, 10 },
                        { INF, 0, 3, INF },
                        { INF, INF, 0, 1 },
                        { INF, INF, INF, 0 } };
 
    // Print the solution
    floydWarshall(graph);
    return 0;
}