최단경로(플로이드 알고리즘)

경로는 a 배열 참조

k는 거쳐가는 노드라고 써있는데 우선 그림을 그려서 이해하면 쉽다.

예를 들어서 k가 현재 0이고 i는 1이라고 치자

i(두번째 행) 에서 네번째 행으로 가는 거리는 inf(무한대)이다. 

하지만 i(현재 두번째 행을 가르킴)에서 k(현재 첫번째행)을 거쳐서 네번째 행으로 가는 거리는

-> 두번째행에서 첫번째행까지의 거리인 5 + 첫번째 행에서 네번째 행까지의 거리 7

합해서 12가 나온다. 12는 inf보다 작으니 해당 요소의 값을 12로 바꿔주는것!

 

마지막 for문은 구한 경로를 출력하는 코드이다.

 

직접 그려서 해보면 더 이해가 쉽다!