최단 경로 알고리즘 - 3. 플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm)

플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm)

플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 그래프에서

가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘이다.

 

핵심 아이디어

거쳐가는 노드를 기준으로 가능한 모든 노드 쌍의 최단 거리를 갱신해 나간다.

 

구현 코드

void floyd_warshall()
{
	// i 노드에서 j노드로 갈 때, k노드를 거쳐서 가는게 더 빠르다면 최단 거리 갱신
	for (int k = 1; k <= N; k++)
	{
		for (int i = 1; i <= N; i++)
		{
			for (int j = 1; j <= N; j++)
			{
				graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
			}
		}
	}
}

 

• 점화식 : D[i][j] = min(D[i][j], D[i][k] + D[k][j])
• 시간 복잡도 : $O(V^3)$

 

관련 문제

[BOJ-11404] 플로이드

#include <iostream>
#include <algorithm>

using namespace std;

const int INF = int(1e9);

int N, M;
int start;

int graph[101][101];

void floyd_warshall()
{
	for (int k = 1; k <= N; k++)
	{
		for (int i = 1; i <= N; i++)
		{
			for (int j = 1; j <= N; j++)
			{
				graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> N >> M;

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			if (i != j)
			{
				graph[i][j] = INF;
			}
			else
			{
				graph[i][j] = 0;
			}
		}
	}

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

		graph[a][b] = min(graph[a][b], c);
	}

	floyd_warshall();

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			if (graph[i][j] != INF)
			{
				cout << graph[i][j] << ' ';
			}
			else
			{
				cout << "0 ";
			}
		}
		cout << '\n';
	}

	return 0;
}

 

[BOJ-11780] 플로이드2

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = int(1e9);

int N, M;
int start;

int graph[101][101];
int nextNode[101][101];

void floyd_warshall()
{
	for (int k = 1; k <= N; k++)
	{
		for (int i = 1; i <= N; i++)
		{
			for (int j = 1; j <= N; j++)
			{
				if (graph[i][k] + graph[k][j] < graph[i][j])
				{
					graph[i][j] = graph[i][k] + graph[k][j];
					nextNode[i][j] = nextNode[i][k];
				}
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> N >> M;

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			if (i != j)
			{
				graph[i][j] = INF;
			}
			else
			{
				graph[i][j] = 0;
			}
		}
	}

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

		graph[a][b] = min(graph[a][b], c);
		nextNode[a][b] = b;
	}

	floyd_warshall();

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			if (graph[i][j] != INF)
			{
				cout << graph[i][j] << ' ';
			}
			else
			{
				cout << "0 ";
			}
		}
		cout << '\n';
	}

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			if (graph[i][j] == 0 || graph[i][j] == INF)
			{
				cout << "0\n";
			}
			else
			{
				vector<int> path;
				int u = i, v = j;
				path.push_back(u);

				while (u != v)
				{
					u = nextNode[u][v];
					path.push_back(u);
				}

				cout << path.size() << ' ';
				for (auto& x : path)
				{
					cout << x << ' ';
				}
				cout << '\n';
			}
		}
	}

	return 0;
}

 

 

이 문제는 최단 거리뿐 아니라 경로까지 알아야 하는 문제이다.

nextNode[i][j]는 i -> j 로의 최단 거리 경로에서 시작 노드 다음의 노드를 저장한다.

이 노드를 따라 최종적으로 다음 노드가 j (목표 노드)가 되는 순간 경로 찾기를 중단한다.