[Algorithm/DP] 최단 경로 알고리즘 : 플로이드-워셜(Floyd-Warshall)

최단 경로 알고리즘

최단 경로 알고리즘은 다음과 같이 경우를 나눠서 사용하는 알고리즘이 다르다.

 

1. 단일 출발점에서 다른 모든 정점까지의 최단 경로를 구하는 경우

  a. Dijkstra's Algorithm (다익스트라 알고리즘): 간선의 양의 가중치만 허용

  b. Bellman-Ford Algorithm (벨만-포드 알고리즘): 간선의 양, 음의 가중치 모두 허용

  c. BFS : 간선의 가중치가 없는 경우

 

2. 그래프 내의 모든 정점 쌍 간의 최단 경로를 구하는 경우

  a. Floyd-Warshall (플로이드-워셜 알고리즘): 간선의 양, 음의 가중치 모두 허용

  b. Johnson's Algorithm (존슨 알고리즘): 간선의 양, 음의 가중치 모두 허용

 

 

이 중 이번에는 플로이드-워셜 알고리즘에 대해 알아보고자 한다.

 

 

 

 

---

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

그래프 내의 모든 정점 쌍 간의 최단 경로를 찾는 데 사용되는 동적 프로그래밍 알고리즘이다. 플로이드-워셜은 음의 가중치를 가진 그래프에서도 작동하며, 음의 가중치 사이클을 감지할 수 있다. 플로이드-워셜 알고리즘의 시간복잡도는 O(N^3)으로 다익스트라의 인접행렬버전과 동일하지만, 구현이 매우 간단하여 다익스트라보다 효율적이다. 구현이 간단하다는 것은 아래에서 확인해보겠다.

 

 

 

 

 

DP 접근법

한개의 정점부터 시작해서 1~n개까지의 모든 정점을 경유 가능한 정점으로 고려하면서, 모든 쌍의 최단 경로의 거리를 계산한다. 임시최적해를 구하고 현재 값과 비교하여 계속해서 최적해를 구해나가는 방법이다.

 

따라서, 부분 문제는 정점 1~k개를 경유 가능한 정점으로 고려해서 정점 i부터 정점 j까지의 모든 경로 중에서 최단 경로 D[i][j]를 구하는 것!

ex) i → j / i → 정점1 → j / i → 정점1 → 정점2 → j / ..... / i → 정점1 → ... → k → j 중에서 최단경로를 구하는 것

 

 

 

 

 

---

수행 과정

k=0

0	5	INF	3	INF
INF	0	INF	INF	4
INF	INF	0	1	2
-1	INF	INF	0	-1
INF	-2	3	2	0

행이 시작점, 열이 도착점인 테이블.

초기 상태는 정점 i에서 정점 j로 직접 가는 경로가 최단 경로로, 가중치를 바로 저장해주면 된다.

 

k=1

0	5	INF	3	INF
INF	0	INF	INF	4
INF	INF	0	1	2
-1	4	INF	0	-1
INF	-2	3	2	0

정점4 → 정점2로 바로 가는 경로보다 정점1을 거쳐 가는 경로가 더 작기 때문에 갱신

 

k=2

0	5	INF	3	9
INF	0	INF	INF	4
INF	INF	0	1	2
-1	4	INF	0	-1
INF	-2	3	2	0

 

k=3

0	5	INF	3	9
INF	0	INF	INF	4
INF	INF	0	1	2
-1	4	INF	0	-1
INF	-2	3	2	0

 

k=4

0	5	INF	3	2
INF	0	INF	INF	4
0	5	0	1	0
-1	4	INF	0	-1
1	-2	3	2	0

 

k=5

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

 

---

코드 (Python)

플로이드 워셜 알고리즘을 쓰는 문제 중 백준의 11404 <플로이드> 문제의 코드를 들고 왔다. 

import sys
input = sys.stdin.readline
INF = int(1e9)

n = int(input())
m = int(input())

graph = [[INF]*(n+1) for _ in range(n+1)]
for i in range(1, n+1):
    graph[i][i] = 0
    
for _ in range(m):
    s, e, w = map(int, input().split())
    graph[s][e] = min(graph[s][e], w)
    
# 거쳐가는 경로 중 더 최단경로가 있으면 갱신    
for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])
            
for i in range(1, n+1):
    for j in range(1, n+1):
        if graph[i][j] == INF:
            print(0,  end=" ")
        else:
            print(graph[i][j], end=" ")
    print()

 

 

 

 

 

---

대표 문제

1389번: 케빈 베이컨의 6단계 법칙

 

11404번: 플로이드

 

1956번: 운동