플로이드 와샬

• 다익스트라 : 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘

• 플로이드 와샬 : '거쳐가는 정점을 기준'으로 최단거리를 구하는 알고리즘 => '모든 정점'에서 '모든 정점'으로의 최단 경로를 구하고 싶을 때. =>마찬가지로 다이나믹 프로그래밍 기술에 의거

각각의 정점이 다른 정점으로 가는 비용

0	5	∞	8
7	0	9	∞
2	∞	0	4
∞	∞	3	0

이제 이 테이블이 의미하는 바는 '현재까지 계산된 최소 비용'이다. 이러한 이차원 배열을 반복적으로 갱신하여 최종적으로 모든 최소 비용을 구해야 한다. 바로 그러한 반복의 기준이 '거쳐가는 정점' 이 된다!

1. 노드1을 거쳐가는 경우

0	5		8
7	0	9
2		0
∞			0

노드 1을 거쳐가는 경우는 위와 같이 6가지 공간만을 갱신주면 된다. 이 때 바로 다음 두식을 비교해주는 방식을 반복한다! => 노드 1을 제외한 노드 2,3,4 가 있을 때, 각 노드 <=> 1을 제외한 경로들에 대해 최솟값 비교 & 최단거리 값 갱신한다! 자기 자신으로 가는 경로가 없을 경우 이 경우도 제외. 1->3 2->4 3->2, 3->4 4->2, 4->3

X->Y 최소 비용 vs X->노드1로 가는 비용 + 노드1 ->Y로 가는 비용 즉, 1을 거쳐서 가는 경우가 더 빠른 경우가 존재한다면 빠른 경우로 최소 비용을 계산한다. 예를 들어 D[2,3]은 D[2,3] 과 D[2,1] + D[1,3] 중에서 더 작은 값으로 교체된다. 따라서 노드1을 거쳐가는 경우 계산하면 다음 표와 같이 구성된다.

0	5	∞	8
7	0	9	15
2	7	0	4
∞	∞	3	0

2. 노드 2를 거치는 경우 => 마찬가지로 2를 제외한 나머지 모드 1,3,4에 대해 2<=>1,3,4 를 제외하고 구하면 된다. 남겨두는 것. 이용하기 위해. 1->1,1->2 2->1,2->2,2->3,2->4 3->2,3->3 4->2,4->4 구해야하는 것 총 6개! 1->3,1->4 3->1,3->4 4->1,4->3

0	5
7	0	9	15
	7	0
	∞		0

D[1][3] vs (D[1][2] + D[2][3]) = ∞ vs (5+9) = 14 D[1][4] vs (D[1][2] + D[2][4]) = 8 vs (5+4) = 8 D[3][1] vs (D[3][2] + D[2][1]) = 2 vs ( 7+7) = 2 D[3][4] vs (D[3][2] + D[2][4]) = 4 vs (7+15) = 4 D[4][1] vs (D[4][2] + D[2][1]) = ∞ vs (∞+7) = ∞ D[4][3] vs (D[4][2] + D[2][3]) = 3 vs (∞+9) = 3

0	5	14	8
7	0	9	15
2	7	0	4
∞	∞	3	0

이런 식으로 노드 X에서 출발, 노드 Y에 도착할 때 ①원래 경우와 ②경유지 K를 거쳐서 가는 경우를 비교해서 더 작은 값으로 갱신시켜 모든 정점 -> 모든 정점 최단거리를 구한다!

① 원래 경우 : D[X][Y] ② 경유지 K를 거쳐서 가는 경우 : D[X][K] + D[K][Y] ③ D[X][Y] = Math.min(D[X][Y],D[X][K] + D[K][Y])