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

양영준·2026년 3월 1일

Algorithm

목록 보기

6/7

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

다익스트라 (Djikstra) 알고리즘은 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘이었다.
플로이드-워셜 (Floyd-Warshall) 알고리즘은 다익스트라 알고리즘에서 확장되어 모든 지점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이다.

플로이드-워셜 알고리즘은 노드의 개수가 N 이라고 할 때, N 번 만큼의 단계를 반복하며 점화식에 맞게 2차원 배열을 갱신하기 때문에 다익스트라 알고리즘과 동일하게 다이나믹 프로그래밍 (Dynamic Programming) 이다.

출발 노드를 a , 도착 노드를 b , 중간 노드를 k 라고 할 때 플로이드-워셜 알고리즘의 점화식은 다음과 같다.

💡 다익스트라 알고리즘과의 차이점 ?

다익스트라 알고리즘은 출발 노드가 1개이므로, 다른 모든 노드까지의 최단 거리를 저장하는 배열을 1차원 배열로 사용했다.
그러나 플로이드-워셜 알고리즘은 모든 노드에 대해서 다른 모든 노드로 가는 최단 거리를 저장해야하기 때문에 2차원 배열을 사용한다.

플로이드-워셜 알고리즘은 다익스트라 알고리즘과 달리 매 단계마다 최단 거리를 갖는 노드를 찾을 필요가 없다.

다익스트라 알고리즘은 간선 간의 가중치가 양수인 경우에만 사용할 수 있지만, 플로이드-워셜 알고리즘은 간선 간의 가중치가 음수인 경우에도 사용할 수 있다.

💡 동작 과정

다음 그래프를 통해 플로이드-워셜 알고리즘의 동작 과정을 살펴보도록 하자.

1. 그래프의 간선 표현

그래프의 간선 정보를 2차원 배열 형태로 표현한다.
각 노드 간의 가중치 값을 기록하며, 간선이 없는 경우 INF 으로 표기한다.

2. 각 노드를 거쳐가는 경우에 대한 최단 거리 갱신

0번 노드부터 차례대로 해당 노드를 거쳐가는 경우에 대한 가중치를 모두 구하여 이미 구한 최단 거리 값들과 비교를 진행한다.
이 때, 노드를 거쳐가는 총 경우의 수는 N - 1P2 개로, 예시 그래프의 경우 3P2 = 6 가지 경우가 존재한다.

현재 노드가 0인 경우, 다음과 같이 갱신된다.

모든 노드에 대한 가중치를 구하고 난 뒤, 2차원 배열 테이블에는 다음과 같이 저장되어 있다.

💡 구현 코드

#define _CRT_SECURE_NO_WARNINGS

#include <vector>
#include <iostream>

using namespace std;

int main()
{
	freopen("input.txt", "r", stdin);

	int N;
	cin >> N;

	vector<vector<int>> graph(N, vector<int>(N));
	for (int i = 0;i < N;i++)
	{
		for (int j = 0;j < N;j++)
		{
			cin >> graph[i][j];

			if (i != j && graph[i][j] == 0)
			{
				/*
                간선이 연결되어 있지 않는 경우에 대한 처리
                INF -> INT_MAX 로 처리했다.
                */
				graph[i][j] = INT_MAX;
			}
		}
	}

	for (int k = 0;k < N;k++)
	{
		for (int a = 0;a < N;a++)
		{
			for (int b = 0;b < N;b++)
			{
				if (graph[a][k] == INT_MAX)
				{
					continue;
				}

				if (graph[k][b] == INT_MAX)
				{
					continue;
				}

				//현재 선택한 노드를 거쳐갈 수 있는 경우 갱신 시도
				graph[a][b] = min(graph[a][k] + graph[k][b], graph[a][b]);
			}
		}
	}

	for (int i = 0;i < N;i++)
	{
		for (int j = 0;j < N;j++)
		{
			cout << graph[i][j] << " ";
		}
		cout << endl;
	}
}