[Greedy] Floyd Algorithm

플로이드 알고리즘

 

최단거리를 찾는 알고리즘입니다.

 

한 노드를 고정시키고 나머지 노드들의 경로의 기존 값과 고정노드를 통한 값을 비교하고 수정합니다.

모든 노드를 거치면 완료됩니다.

 

Ak[i,j] = min ( Ak-1[i,j] , Ak-1[i,k] + Ak-1[k,j] )

 

ex)

A0	N1	N2	N3	N4
N1	0	7	∞	3
N2	2	0	∞	∞
N3	5	1	0	∞
N4	8	∞	2	0

A1 = 1 고정 (1행 & 1열 & 대각 고정)

다른 노드들의 기존 값과 노드1을 거쳐가는 경우를 비교

A1[2,3] = min( A0[2,3],  A0[2,1] + A0[1,3] ) = min( ∞, 2 + ∞ ) = ∞

A1[2,4] = min( A0[2,4],  A0[2,1] + A0[1,4] ) = min( ∞, 2 + 3 ) = 5

...

A1	N1	N2	N3	N4
N1	0	7	∞	3
N2	2	0	∞	5
N3	5	1	0	8
N4	8	15	2	0

...

A4 까지 반복

A4	N1	N2	N3	N4
N1	0	6	5	3
N2	2	0	7	5
N3	3	1	0	6
N4	5	3	2	0