Floyd의 최단 경로 구하기

동적 프로그래밍의 이해를 돕고자 Floyd의 최단 경로 알고리즘을 구현해보았다.

 

컴파일러: Dev-C++ 4.9.9.2

 

floyd.cpp

 

[풀이]

 

최단 경로 알고리즘은 동적 프로그래밍을 바탕으로 해결된다.

 

A, B, C, D 가 있다고 하자. A-C를 직접 이은 값보다 A-B-C를 이은 값이 적다면 후자가 최단 경로일 것이다.

 

이 값을 버퍼에 넣고, 다음에 A-D-C를 이은 값과 비교한다.

 

중요한 점은 다른 점들도 동시에 비교를 해야한다. 즉, A-D-C를 하기 전에 이미 A-D에 최적 경로와 D-C에 대한 최적 경로가 구해져야하는 것이다. 이는 동적 프로그래밍의 성립 조건이기도 하다.

 

그에 따라, 노드 개수만큼 그래프의 자료 구조를 탐색해야 한다. 알다시피 그래프의 자료 구조는 행과 열로 이루어진다. 이에 따라 프로그램은 세개의 루프로 구성되며, 시간 복잡도는 노드 개수의 3승이 된다.