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

이때동안 포스팅한 최단거리 알고리즘은 벨만포드, 다익스트라 알고리즘이 있습니다.

이 두개의 알고리즘은 하나의 정점을 기준으로 다른 정점들까지의 최단거리를 구하는 알고리즘입니다.

플로이드 워셜 알고리즘은 이들과 달리 모든 정점간의 최단거리를 구하는 알고리즘입니다.

 

플로이드 워셜 알고리즘의 기본 원리는 i 정점에서 j 정점 간의 최단거리를 구하려고 할 때,

그 외의 노드 k를 두고 i -> k 로 이동하는 방법이 존재하고 k -> j로 이동하는 방법이 존재할 때,

k를 거쳐서 가는 거리가 이때동안 구한 최단거리보다 더 짧을 때, 최단거리를 갱신하는 방법입니다.

 

---

정점들의 번호가 0~n-1, i에서 j로 가는 거리(간선)가 W(i, j)이고 최단거리를 배열 dist에 저장한다고 할 때,

플로이드 워셜 알고리즘은 다음과 같습니다.

 

먼저 모든 간선(W 값)으로 dist 배열을 갱신합니다.

for (int k = 0; k < n; k++)
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if(dist(i, k), dist(k,j) 가 존재하고 dist[i][j] > dist[i][k] + dist[k][j] 라면)
	           dist[i][j] = dist[i][k] + dist[k][j]

 

정점의 개수가 V, 간선의 개수를 E라 했을 때, 플로이드 워셜 알고리즘은 정점의 개수만큼 3차 for문을 돌게 되므로

시간복잡도는 O(V^3)이 됩니다.

---

플로이드 워셜 알고리즘을 사용하는 기본 문제입니다.

플로이드(11404) : https://www.acmicpc.net/problem/11404

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/BOJ/11404.%20%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C.cpp