[그래프] 플로이드-워셜 Floyd-Warshall

플로이드-워셜 Floyd-Warshall

모든 정점 사이의 최단 경로를 구하는 알고리즘

요약

1) a->b로 가는 거리와, 특정 정점 k를 거쳐서 가는 거리(a->k + k->b) 중 작은 것을 고름

2) 모든 정점을 거쳐서 가는 경우를 비교! => N번의 라운드 (k = 0 ~ n-1)

전제

1) 연결되지 않은 정점의 거리는 INF(최댓값)로, 연결된 정점은 1로 저장(=최단 경로가 1)

2) 자기 자신에게 가는 거리는 0

ex) 3개의 정점(0, 1, 2)이 있다.
간선의 정보는 아래와 같다.
0 -> 1
1 -> 2
2 -> 0

이 경우 정점 간 거리 그래프는 아래와 같다.
(M = INF)
  0 1 2
0 0 1 M 
1 M 0 1
2 1 M 0

이 그래프의 각 점에서의 최단 경로는 아래와 같다.
  0 1 2
0 0 1 2 
1 2 0 1 
2 1 2 0

(해석) graph[1][0] = 2
=> 1에서 0으로 가는 최단 경로: 2
1 -> 2 -> 0

---

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

다익스트라	플로이드-워셜
한 정점으로부터의 최단 경로	모든 정점으로부터의 최단 경로
음의 가중치 허용 x	음의 가중치 허용 o

---

코드(Python)

# 중간 정점 k = 0 ~ n-1
for k in range(n):
    for a in range(n):
        for b in range(n):
        	# a에서 b로 가는 최단 거리를 저장
            # a->b로 가는 거리 vs k를 거쳐서 가는 거리 비교
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])