플로이드-워셜(Floyd-warshall) 알고리즘

📌 정의

 

시작점을 지정하지 않고 그래프에서 모든 노드와 관련된 최단 거리를 구하는 알고리즘

 

📌 주요 특징

 

기능	특징	시간 복잡도(노드 수: V)
모든 노드 간에 최단 경로 탐색	- 음수 가중치 Edge가 있어도 수행 가능 - 동적 계획법의 원리를 이용해 알고리즘에 접근	O(V^3)

 

📌 핵심 이론

 

최단 경로를 구했다고 가정했을 때, 그것을 이루는 부분 경로 역시 최단 경로이다.

 

예를 들어, A에서 B까지 최단 경로를 구했다고 가정한다. 이때, 해당 경로 위에 K 노드가 존재한다면 A에서 K 노드를 거쳐 B에 도착하는 경로 역시 최단 경로라는 것이다. 따라서 점화식은 다음과 같이 도출된다.

 

D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])

 

📌 접근 방법

 

🔎 초기 배열

 

D[S][E]는 노드 S에서 E까지의 최단 거리를 저장하는 배열이다. 자기 자신에게 가는 경로가 없을 때, 최단 경로값은 0이고, 나머지는 매우 큰 값으로 지정한다.

 

문제

 

S/E	1	2	3	4	5
1	0	∞	∞	∞	∞
2	∞	0	∞	∞	∞
3	∞	∞	0	∞	∞
4	∞	∞	∞	0	∞
5	∞	∞	∞	∞	0

 

🔎 가중치 인접 행렬

 

S/E	1	2	3	4	5
1	0	8	3	∞	∞
2	∞	0	∞	-4	15
3	∞	∞	0	13	∞
4	∞	∞	∞	0	2
5	∞	∞	∞	5	0

 

🔎 점화식

 

3중 for 문으로 검사한다. 첫 번째 루프는 모든 경유지이고, 두 번째는 출발지, 마지막 루프는 목적지다. 해당 루프 내에서 위의 점화식을 대입하면 한 번에 도착했을 때와 경유지를 거쳤을 때의 가중치를 비교하여 최단 거리를 구한다. 이것이 성립할 수 있는 이유는 플로이드-워셜의 이론인 최단 경로 내 부분 경로가 최단 경로를 보장하기 때문이다.

 

for 경유지 K:
    for 출발 노드 S:
        for 목적지 노드 E:
            D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E]);

 

S/E	1	2	3	4	5
1	0	8	3	4	6
2	∞	0	∞	-4	-2
3	∞	∞	0	13	15
4	∞	∞	∞	0	2
5	∞	∞	∞	5	0

 

Reference: