[그래프 알고리즘]플로이드 워셜 알고리즘

모든 쌍 최단거리 알고리즘

플로이드 워셜 알고리즘은 그래프상의 모든 노드 쌍에 대한 최단 거리를 계산합니다.

모든 노드쌍에 대한 최단 거리를 계산하기 때문에 보통 2차원 배열에 최단 거리를 저장합니다.

노드 u 에서 노드 v로의 최단 거리는 2차원 배열 u행 v열에 저장합니다.

최단거리 업데이트 : 경유점

최초로 주어지는 최단 거리 2차원 배열은 바로 인접한 엣지의 가중치입니다.

노드 u와 노드 v 사이의 거리는 다른 노드들을 거친다고 할 때 더 짧아질 수 있으면 업데이트할 수 있습니다.

최단거리 배열 dist[u][v]의 값이 노드 k를 거친 값 dist[u][k] + dist[k][v] 보다 크다면,

dist[u][v]를 dist[u][k] + dist[k][v] 값으로 업데이트합니다.

이를 모든 노드에 대해 계산하면, 2차원 배열의 값은 모든 노드들이 k를 거칠 수 있을 때의 최단 거리가 됩니다.

이제 k에 모든 노드들을 하나씩 대입해서 계산하면 2차원 배열의 값은 모든 노드들간의 최단거리가 됩니다.

구현