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

October 25, 2024

플로이드 워셜(Floyd-Warshall) 알고리즘은 모든 노드에서 다른 모든 노드까지의 최단 경로를 한 번에 구하는 알고리즘입니다. 다익스트라가 단일 출발점의 최단 경로를 구하는 것과 달리, 플로이드 워셜은 모든 쌍(Pair)에 대한 최단 거리를 구할 수 있습니다.

또한 플로이드 워셜은 DP(동적 계획법) 알고리즘에 속합니다. N번의 단계를 반복하며 점화식에 맞게 2차원 테이블을 갱신하기 때문입니다.

다익스트라 vs 플로이드 워셜

구분	다익스트라	플로이드 워셜
최단 경로 범위	단일 출발점 → 다른 모든 노드	모든 노드 쌍
거리 저장 구조	1차원 배열	2차원 배열
알고리즘 유형	그리디	DP
음수 가중치	❌	✅
시간 복잡도	O(E log V)	O(N³)
구현 난이도	보통	쉬움

다익스트라는 매 단계마다 방문하지 않은 노드 중 최단 거리 노드를 선택하지만, 플로이드 워셜은 '거쳐 가는 노드'를 기준으로 테이블을 갱신하므로 최단 노드를 별도로 찾을 필요가 없습니다.

핵심 아이디어: 점화식

플로이드 워셜의 핵심은 아래 점화식입니다.

dist[a][b] = min(dist[a][b], dist[a][k] + dist[k][b])

dist[a][b]: 노드 a에서 노드 b까지의 현재 최단 거리
dist[a][k] + dist[k][b]: 노드 k를 경유해서 a → b로 가는 거리

즉, "k번 노드를 거쳐서 가는 것이 더 짧다면 갱신한다" 는 원리입니다. 이 과정을 모든 노드 k에 대해 반복하면 모든 쌍의 최단 거리가 구해집니다.

동작 단계

2차원 거리 테이블 dist[N+1][N+1]을 INF로 초기화합니다.
자기 자신으로 가는 거리 dist[i][i]는 0으로 설정합니다.
입력된 간선 정보로 테이블을 초기화합니다.
모든 노드 k에 대해 아래를 반복합니다. (k = 경유 노드)
- 모든 노드 쌍 (a, b)에 대해 점화식을 적용해 테이블을 갱신합니다.

동작 예시

아래 그래프를 기준으로 단계별 테이블 변화를 확인합니다.

노드: 1, 2, 3, 4
간선: 1→2(4), 1→4(6), 2→1(3), 2→3(7), 3→1(5), 3→4(4), 4→3(2)

[초기 테이블] 직접 연결된 간선만 반영

	1	2	3	4
1	0	4	∞	6
2	3	0	7	∞
3	5	∞	0	4
4	∞	∞	2	0

[Step 1] 노드 1을 경유하는 경우 반영

예: dist[2][4] = min(∞, dist[2][1] + dist[1][4]) = min(∞, 3+6) = 9

	1	2	3	4
1	0	4	∞	6
2	3	0	7	9
3	5	9	0	4
4	∞	∞	2	0

[Step 2] 노드 2를 경유하는 경우 반영

예: dist[1][3] = min(∞, dist[1][2] + dist[2][3]) = min(∞, 4+7) = 11

	1	2	3	4
1	0	4	11	6
2	3	0	7	9
3	5	9	0	4
4	∞	∞	2	0

[Step 3, 4] 노드 3, 4를 경유하는 경우 반영 후 최종 테이블

	1	2	3	4
1	0	4	8	6
2	3	0	7	9
3	5	9	0	4
4	7	11	2	0

Python 구현

import sys

INF = int(1e9)

def floyd_warshall(n, edges):
    # 2차원 거리 테이블 초기화
    dist = [[INF] * (n + 1) for _ in range(n + 1)]

    # 자기 자신으로 가는 비용은 0
    for i in range(1, n + 1):
        dist[i][i] = 0

    # 간선 정보로 테이블 초기화
    for a, b, c in edges:
        dist[a][b] = c

    # 점화식: 노드 k를 경유하는 경우를 모든 쌍에 대해 갱신
    for k in range(1, n + 1):
        for a in range(1, n + 1):
            for b in range(1, n + 1):
                dist[a][b] = min(dist[a][b], dist[a][k] + dist[k][b])

    return dist


# 사용 예시
def main():
    n = int(input())   # 노드 수
    m = int(input())   # 간선 수

    edges = []
    for _ in range(m):
        a, b, c = map(int, input().split())
        edges.append((a, b, c))

    dist = floyd_warshall(n, edges)

    # 결과 출력
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            if dist[a][b] == INF:
                print("INF", end=" ")
            else:
                print(dist[a][b], end=" ")
        print()


main()

입력 예시

출력 예시

음수 순환 감지

플로이드 워셜 수행 후 dist[i][i] < 0인 노드가 있다면 음수 순환이 존재하는 것입니다. 자기 자신으로 돌아오는 경로의 비용이 음수라는 의미이기 때문입니다.

# 음수 순환 감지
for i in range(1, n + 1):
    if dist[i][i] < 0:
        print("음수 순환 존재")
        break

시간 복잡도

구조	복잡도
경유 노드 k 반복	O(N)
모든 쌍 (a, b) 확인	O(N²)
전체	O(N³)

노드 수가 많아질수록 연산량이 급격히 증가합니다. 일반적으로 노드 수가 500 이하인 경우에 적합합니다.

최단 경로 알고리즘 종합 비교

알고리즘	최단 경로 범위	음수 가중치	시간 복잡도	적합한 상황
다익스트라	단일 출발점	❌	O(E log V)	노드/간선이 많고 양수 가중치
벨만-포드	단일 출발점	✅	O(VE)	음수 가중치, 음수 순환 감지 필요
플로이드 워셜	모든 쌍	✅	O(N³)	노드 수가 적고 모든 쌍 최단 경로 필요