[알고리즘] 플로이드-와샬 알고리즘

개요

다익스트라 알고리즘은 하나의 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이라면, 플로이드-와샬 알고리즘은 모든 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이다.

이차원 배열을 사용해 최소값을 계속 저장해두기 때문에, 다이나믹 프로그래밍 기법의 일부로도 볼 수 있다.

 

설명

A에서 B로 가는 최소 비용과 A에서 C를 거쳐 B로 가는 최소 비용을 비교한다.

 

다음과 같은 비용을 가지는 양방향 그래프가 있다고 가정하다.

초기값을 먼저 표시하면 다음 표와 같다.

1을 지날 때 다음 영역을 갱신 해줘야 한다.

4 -> 1-> 5 (반대도 같음)의 비용이 14이므로 INF에서 갱신해준다.

 

2를 지날 때

3 -> 2 -> 4 (반대도 같음)의 비용이 7로, 기존의 비용 8보다 더 저렴하다. 갱신해준다.

 

3을 지날 때

4 -> 3 -> 5의 비용이 8로, 기존의 비용 14보다 더 저렴하므로 갱신해준다.

 

4를 지날 때

5를 지날 때

 

구현

출발노드 i

도착노드 j

거쳐가는 노드를 k라고 한다.