모든 쌍의 최단 경로를 구하는 방법을 찾고 싶다면, 다익스트라(Dijkstra) 알고리즘을 모든 정점(Vertex)에 대한 최단경로를 구하거나 다익스트라가 제한되는 경우(음의 가중치가 존재하는 경우)에는 벨만-포드(Bellman-Ford) 알고리즘을 모든 정점(Vertex)에 대해서 사용하면 된다.
플로이드-워셜(Floyd-Warshall) 알고리즘은 앞서 말한 두 알고리즘과는 다르게 처음부터 모든 정점 사이의 최단 경로를 구하는 알고리즘이다.
위 그림은 i에서 j로 가는 방법을 표현한 것으로, k를 경유하는 경우와 그렇지 않은 경우에 대한 것이다.
위 문자의 의미는 1부터 k까지만 경유할 수 있는 상황에서 i에서 j까지 갈 수 있는 모든 경로 중, 가장 짧은 경로의 거리로, 동적계획법(Dynamic Programming)의 부분해에 해당한다. 특정 경로만 경유할 수 있는 상황에서 A에서 B까지의 모든 경로 중 가장 짧은 경로의 거리를 계산해 나가는 방법은 동적계획법의 점화식 정립 과정이라고 생각하면 된다.
위 그림을 다시 살펴보자, 이런 상황이 주어졌을 때 두 가지 경우를 따져볼 수 있다. k를 경유할 때와 그렇지 않을 때의 누적 가중치 값을 비교해 작은 경로를 채택하는 것이 답일 것이다.
위 그림을 바탕으로 한 점화식은 다음과 같으며, 이것이 플로이드-워셜 알고리즘의 핵심이다.
의사 코드(Pseudo Code)
Input
2차원 배열 D, D[i][j]는 i->j의 가중치, 경로가 없는 경우에는 D[i][j]=INF(무한)으로 정의하며, D[i][i]=0
Output
모든 쌍의 최단 경로 정보를 담은 배열 D
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
D[i][j]=min(D[i][k]+D[k][j], D[i][j])
소스 코드(Source Code)
#include <iostream> #define INF 1000000000 using namespace std; int graph[100][100], n; void Floyd() { for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (graph[i][k] + graph[k][j] < graph[i][j]) graph[i][j] = graph[i][k] + graph[k][j]; } int main(void) { int b, v1, v2, w; cin >> n; // 배열값을 INF로 초기화 // 경로 정보가 갱신되지 않으면 경로가 없는 것으로 간주 for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) graph[i][j] = INF; // D[i][i]=0 for (int i = 0; i < n; i++) graph[i][i] = 0; // 경로 정보 입력, v1->v2, weight(w) cin >> b; for (int i = 0; i < b; i++) { cin >> v1 >> v2 >> w; if (graph[v1 - 1][v2 - 1] > w) graph[v1 - 1][v2 - 1] = w; } Floyd(); // 경로가 없는 경우 INF를 출력 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (graph[i][j] == INF) cout << 'INF '; else cout << graph[i][j] << ' '; } cout << '\n'; } }
시간 복잡도(Time Complexity)
O(V^3), V는 정점 수
공간 복잡도(Space Complexity)
O(V^2), V는 정점 수
응용 분야
네비게이션, GIS 네트워크 분석, VLSI 디자인 등
'Computer Science > Data Structure, Algorithm' 카테고리의 다른 글
두근두근 자료구조 2장 프로그래밍 프로젝트 1번 (1) | 2018.04.12 |
---|---|
두근두근 자료구조 2장 연습문제 (0) | 2018.04.11 |
DataStructure] 힙(Heap, 히프) 만들기 - 2 (0) | 2017.08.20 |
DataStructure] 힙(Heap, 히프) 만들기 - 1 (0) | 2017.08.04 |
Algorithm] Segment Tree(구간 트리) - 1 (0) | 2017.08.01 |