플로이드 와샬

• 플로이드 와샬
• • 변의 가중치가 음이거나 양인 가중 그래프에서 최단경로를 찾는 알고리즘
  • 알고리즘 한번 수행시 모든 꼭짓점 쌍 간의 최단 경로의 길이(가중치의 합)을 찾는다.

1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)

2 for each edge (u,v)

3    dist[u][v] ← w(u,v)  // 변 (u,v)의 가중치

4 for each vertex v

5    dist[v][v] ← 0

6 for k from 1 to |V|

7    for i from 1 to |V|

8       for j from 1 to |V|

9          if dist[i][j] > dist[i][k] + dist[k][j]

10             dist[i][j] ← dist[i][k] + dist[k][j]

11         end if

k=0일떄	1	2	3	4
1	0	무한	-2	무한
2	4	0	3	무한
3	무한	무한	0	2
4	무한	-1	무한	0

k=1 즉, 1번 다리를 이어줘 본 것임

k=1일떄	1	2	3	4
1	0	무한	-2	무한
2	4	0	3	무한
3	무한	무한	0	2
4	무한	-1	무한	0