그래프 이론 - 플로이드워셜 알고리즘

나무위키를 기반으로 정리하였습니다.

플로이드 워셜을 그래프에서 가능한 모든 노드 쌍에 대한 최단 거리를 구하는 알고리즘입니다.

 

data[a][b] = min(data[a][b], data[a][k]+data[k][b])

가 핵심코드입니다. 

a-> b 로 바로 가는게 더 빠르냐

a->k->b 로 k를 거쳐서 가는게 더 빠르냐

더 빠른 놈으로 data[a][b]를 업데이트해라. 

 

내가 헷갈렸던 부분은,

D(2,3) = min(D(2,3),D(2,1)+D(1,3))이라고 하자.
이때 k는 1이다.

만약 D(2,1) 의 최소가 D(2,5)+D(5,1)이라면, 최적이 되는가?

였다.

 

이에 대한 답은 아래와 같다.

2->5->3이서 최솟값이 되는 과정은 (2->5->1)->3 순이 아니라 2-> ( 5->1->3) 순으로 최솟값들이 업데이트 된다는 것이다.

 

개념에 대한 자세한 설명은 나무위키를 참고하자~

https://namu.wiki/w/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

플로이드-워셜 알고리즘 - 나무위키