최단경로 알고리즘(3)/ 플로이드 워셜 알고리즘

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서와 유튜브 강의를 참고하며 작성하였습니다. 

코드 출처: https://github.com/ndb796/python-for-coding-test

---

▶ 플로이드 워셜 알고리즘이란?

모든 노드에서 다른 모든 노드까지의 최단경로를 계산하는 알고리즘으로 단계별로 거쳐가는 노드를 기준으로 알고리즘을 수행한다. 2차원 테이블에 최단거리 정보를 저장하고 점화식에 따라 거리 정보를 갱신하는 원리로 다이나믹 프로그래밍 유형에 속한다. 점화식은 각 단계 즉 k의 노드를 점검할 때마다 a에서 b로 가는 거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧을 때 해당 값으로 거리정보를 갱신하는 원리를 사용한다. 따라서 점화식은 다음과 같다. 

 

Dab= min(Dab, Dak+ Dkb)

 

> 시간복잡도: N이 노드의 개수를 의미할 때, 각 단계마다 O(N^2)연산이 이뤄지기 때문에 총 시간 복잡도는 O(N^3)이다. 따라서 문제를 풀때 N이 500이하일 때 시간초과 판정을 받지 않을 가능성이 크다. 

 

▷ 예시

실제로는 1번에서 4번 노드까지 알고리즘을 수행해야하지만 예시로는 1번과 2번 노드를 거쳐가는 경우만 생각하여 이해를 돕고자 하였다. 

> 1번을 걸쳐가는 경우이다. 먼저 자기 자신에 대해서는 모두 거리 0을 넣어준다. 그 후 출발 노드에서 도착노드로 가는 거리 비용과 출발 노드에서 1번 노드를 거쳐 도착노드로 가는 거리 비용 중 더 작은 값을 2차원 테이블에 갱신해주는 과정을 반복한다. 그럼 첫번째 테이블이 만들어진다. 

> 2번을 거쳐가는 경우이다. 첫번째와 마찬가지로 2번을 거쳐가는 경우의 거리와 거쳐가지 않는 경우의 거리를 비교했을 때 더 짧은 비용으로 테이블을 갱신해준다. 두번째 테이블에서는 갱신된 값이 빨간색으로 표시한 노드 3에서 노드 1로 가는 거리밖에 없다. 해당 값은 원래 첫번째 단계에서 3에서 1로 가는 노드가 없었기 때문에 INF값 그대로 였는데 두번째 단계에선 3에서 2를 거쳐 1로 갈 수 있는 간선이 존재하기 때문에 4+2=6으로 값을 갱신할 수 있었다. 

> 3, 4번 노드까지 같은 방식으로 계산하여 테이블을 갱신하면 모든 노드의 최단거리 테이블이 완성된다. 

 

▷ 구현

예시의 그래프를 참고하여 값을 넣은 후 3중 반복문을 통해 알고리즘을 구현한다. 

 

노드 4까지 알고리즘을 수행한 결과, 인덱스 1행부터 4행, 1열부터 4열까지가 모든 노드로의 최단거리 정보를 담은 배열이다.