그래프 이론 - 플로이드워셜 알고리즘
나무위키를 기반으로 정리하였습니다. 플로이드 워셜을 그래프에서 가능한 모든 노드 쌍에 대한 최단 거리를 구하는 알고리즘입니다. 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) ..