플로이드-와샬 알고리즘(Floyd-Warshall Algorithm)

이 알고리즘은 시작정점A -> 시작정점B 까지 이르는 비용을 모두 구할 수 있는 알고리즘이다.

어떤 경유지점 지정하고, 출발점과 도착점을 지정했을 때 해당 값으로 갱신을 함.

위와 같은 경우에서 
출발지에서 경유지를 지나 도착지로 가는 경우에 더 빠르게 가는 경우가 있을 수 있다.
그때의 최단 경로를 갱신해주는 것이 플로이드 와샬 알고리즘인데...

일단 정점의 갯수만큼! 행렬을 이차원배열을 만들어야 한다. 
이차원 배열을 만들 때 G[시작][도착] 을 기준으로 만들게 되면,
시작==도착 이 같은 경우는 0으로 설정한다. 혹은 -INF 자기 자신으로 오는 경우를 제외
시작!=도착 이 다른 경우는 INF 으로 설정한다. 그래야 더 작은 값이 들어 왔을 때 갱신을 할 수 있음.

 

시작\도착	0	1	2	3	4
0	- ∞	∞	∞	∞	∞
1	∞	- ∞	∞	∞	∞
2	∞	∞	- ∞	∞	∞
3	∞	∞	∞	- ∞	∞
4	∞	∞	∞	∞	- ∞

그리고 입력으로
출발정점, 도착정점이르는 간선 cost 가 주어지면 
해당 G의 G[출발][도착] = min(G[출발][도착],cost) 으로 더 낮은 간선을 초깃값으로 지정한다.
그렇게 지정을 한 후, 경유지-출발지-도착지 순으로 loop를 순회시킨다. 
그리고 
가장 안쪽 도착지 loop에서 
if(G[출발][도착] > G[출발][경유] + G[경유][도착) 인 갱신 조건문을 넣어 
값이 더 작은 경우 갱신을 시킨다.
순서만 기억해두면 될 것 같다는 생각......

1 2 3 4 5

for ~ 경유지 k   for ~ 출발지 i     for ~ 도착지 j       if(G[i][j] > G[i][k] + G[k][j])         G[i][j] = G[i][k] + G[k][j];

cs