플로이드-워셜 알고리즘
작성 완료
- 변의 가중치가 음이거나 양인 (음수 사이클은 없는) 가중 그래프에서 최단 경로들을 찾는 알고리즘
- 알고리즘을 한 번 수행하면 모든 꼭짓점 쌍 간의 최단 경로의 길이 (가중치의 합)을 찾는다
- $1$에서 $N$까지 번호가 매겨진 $V$를 꼭짓점으로 가지는 그래프 $G$를 고려하자
- $D(i,j,k)$를 $i$에서 $j$로 가는데 집합 $\{1,2,\cdots,k-1,k\}$의 꼭짓점만을 경유지로 거쳐가는 최단 경로를 반환하는 함수라고 하자
- 여기서 $D(i,j,k)$는 꼭짓점 $k$를 거치지 않는 경우(1)와 거치는 경우(2)로 나눌 수 있다
- (1)번의 경우
- $i$에서 $j$로 가는데 집합 $\{1,2,\cdots,k-2,k-1\}$의 꼭짓점만을 경유지로 고려하므로 $D(i,j,k)=D(i,j,k-1)$이다
- (2)번의 경우
- $i$에서 $j$로 가는데 경유지로 꼭짓점 $k$를 거치므로 최단 경로는 $i\to k \to j$가 된다
- $i\to k$와 $k\to j$를 생각하면 둘 모두 집합 $\{1,2,\cdots,k-2,k-1\}$의 꼭짓점만을 경유지로 고려한다
- 즉, (2)번의 경우 $D(i,j,k)=D(i,k,k-1)+D(k,j,k-1)$이다
- 따라서 $D(i,j,k)=\min\left(D(i,j,k-1),D(i,k,k-1)+D(k,j,k-1)\right)$이다
- $k=1$일 때의 $D(i,j,k)$를 구하고 이를 바탕으로 $k=2$일 때를 계산하는 식으로 $k=N$일 때까지 반복하면 모든 $(i,j)$쌍에 대해서 최단 경로를 찾을 수 있다
def floyd_warsahll(graph):
INF = 1e9 ## 무한을 의미
dist = [[INF] * (V + 1) for _ in range(V + 1)] ## V는 꼭짓점의 개수(=그래프에 존재하는 노드의 개수)
## 노드 번호가 1부터 시작하는데 파이썬 인덱스는 0부터 시작하므로 (V + 1) X (V + 1) 크기의 배열로 구성했다
for edge in graph:
u, v, w = edge ## 노드 u, 노드 v, u와 v 사이 간선의 가중치 w
dist[u][v] = w
for v in range(V):
dist[v][v] = 0 ## 여기서 v는 vertex(꼭짓점), 당연하게도 v와 v 사이 간선의 가중치는 0이다 (애초에 간선이 없음...)
## bottom up 방식으로 구현한 동적계획법
for k in range(1, V + 1): ## 경유지: {1, 2, ..., k-1}
for i in range(1, V + 1):
for j in range(1, V + 1):
if dist[i][j] > dist[i][k] + dist[k][j]: ## 기존의 i -> j보다 더 짧은 경로가 존재하면
dist[i][j] = dist[i][k] + dist[k][j] ## relaxation
else:
pass ## 이 경우 D(i, j, k) = min[D(i, j, k-1), D(i, k, k-1) + D(k, j, k-1)] = D(i, j, k-1)
## 어차피 D(i, j, k)와 D(i, j, k-1)의 값이 같으니 아무것도 안해도 됨 (갱신할 필요가 없음)
## 위의 for문은 모든 i와 j에 대해서 i = j일 때도 값을 갱신하려고 한다
## 초기에 dist[v][v] = 0으로 값을 설정했다
## 경로 [i -> ... -> k -> ... -> i]는 길이가 0보다 작을 때만 개선되므로
## 만약 알고리즘이 종료된 후에 모든 v에 대해 dist[v][v]가 음수라면 그래프내에 음수 사이클이 존재함을 의미한다
- 간단한 코드 수정을 통해 두 끝점 사이의 실제 경로를 재현해보자
def floyd_warsahll(graph):
INF = 1e9 ## 무한을 의미
dist = [[INF] * (V + 1) for _ in range(V + 1)]
next_node = [[False] * (V + 1) for _ in range(V + 1)]
for edge in graph:
u, v, w = edge
dist[u][v] = w
next_node[u][v] = v ## k = next_node[u][v]라고 하면 u -> k -> ... -> v를 의미, 즉 u에서 v로 가기위해 노드 u 다음으로 가야할 노드를 나타냄
for v in range(V):
dist[v][v] = 0
for k in range(1, V + 1): ## 경유지: {1, 2, ..., k-1}
for i in range(1, V + 1):
for j in range(1, V + 1):
if dist[i][j] > dist[i][k] + dist[k][j]: ## 기존의 i -> j보다 더 짧은 경로가 존재하면
dist[i][j] = dist[i][k] + dist[k][j] ## relaxation
## 기존에는 i -> j가 최단경로였지만 갱신되면서 i -> ... -> k -> ... -> j가 최단 경로로 바뀜
## i -> j로 가는 최단 경로는 i -> k의 최단 경로와 j - > k의 최단 경로의 합이므로
## i에서 j로 가기위해 거쳐야 할 다음(next) 노드는 실질적으로 i에서 k로 가기위해 거쳐야 할 다음(next) 노드와 같다
next_node[i][j] = next_node[i][k]
def path(u, v, next_node):
if not next_node[u][v]: ## u에서 v로 가는 경로가 없다면
return [] ## 빈 리스트
path = [u] ## 출발 노드
while u != v: ## u에서 출발하여 v에 도착할때까지
## 현재 상황: u -> k -> k2 -> k3 -> ... -> v
## next_node[u][v] = k
## u를 k로 갱신!, 그리고 path에 갱신된 u를 append
## k -> k2 -> k3 -> ... -> v
## 다시 k에 대해 이를 반복!
## 언제까지? v에 도착해서 u와 v가 똑같아질 때까지!
u = next_node[u][v]
path.append(u)
return path
- 위의 코드로 경로를 재현하는 것이 가능한 이유는 최당 경로의 부분 경로 또한 최단 경로이기 때문이다
- $u$에서 $v$로 가는 최단 경로를 $s$라고 하자
- $s$의 부분 경로를 $t$라고 하자
- 여기서 $t$는 $u\to x$이다, 즉 $s$는 $u\to x\to v$
- 만약 $u$에서 $x$로 가는 최단 경로가 $t$가 아니라 $p$라고 해보자
- 그러면 기존의 경로 $u\to x\to v$에서 $u$에서 $x$로 갈 때 $t$가 아닌 $p$로 가는 것이 더 짧다
- 즉 $s$에서 $t \to v$가 아닌 $p\to v$가 더 짧은 경로이고 이는 $s$가 $u$에서 $v$로 가는 최단 경로라는 가정에 모순된다
- 따라서 귀류법에 의해 최단 경로의 부분 경로 또한 최단 경로이다
- 아래에서 $V$는 노드의 개수이고 $E$는 간선의 개수이다
- 위에서 구현한 플로이드-워셜 알고리즘 코드 내부를 보면 for문이 3번 중첩되어 있고 각 for문은 $V$번 동작한다
- 따라서 시간복잡도는 $O\big(V^3\big)$이다
- 공간복잡도는 $(V+1) \times (V+1)$ 크기의 2차원 배열을 사용하므로 $O\big(V^2\big)$이다
- 경로를 재현하는 part는 $O(E)$의 시간복잡도와 $O(V)$의 공간복잡도이다
- $u\to v$에서 최악의 경우 모든 간선을 거쳐야하므로 시간복잡도는 $O(E)$이고
- 이때의 경로는 모든 노드를 포함하므로 이를 담기 위한 $O(V)$크기의 배열이 필요, 따라서 공간복잡도는 $O(V)$이다