[개념 정리] 최단거리 알고리즘 - 플로이드 와샬

가중치가 없는 그래프의 최단거리 문제는 대부분 BFS로 해결할 수 있습니다. 하지만, 간선에 가중치가 존재한다면 BFS가 아닌 최단거리 알고리즘을 통해 접근해야 합니다. 일반적으로 가중치 그래프의 최단거리 문제는 다음과 같은 유형이 존재합니다.

1. 두 정점 간의 최단 거리를 구하는 문제
2. 하나의 정점에서 다른 모든 정점과의 최단거리를 구하는 문제
3. 하나의 정점으로 가는 모든 최단 경로를 구하는 문제
4. 정점 간의 모든 최단 경로를 구하는 문제

이 중 4번을 해결하기 위한 플로이드-와샬 알고리즘에 대해 알아보고자 합니다.

---

플로이드 와샬 알고리즘

플로이드 와샬 알고리즘은 모든 정점간의 최단경로를 구하는 알고리즘입니다. 앞으로의 설명에서 사용될 그래프는 다음과 같은 가중치를 가지고 있습니다. 

발로 그린 그림

 

초기 가중치 값을 저장하는 인접 행렬(D)은 다음과 같습니다.

인접 행렬 D

초기 인접행렬을 최단 경로 행렬로 만드는 방법을 간단히 설명해 보면 K번째 노드를 추가했을 때, 정점 i에서 j까지의 최단거리는 기존에 i ⇒ j의 거리와 중간에 k를 거쳐가는 거리 중 짧은 거리가 됩니다.

위의 점화식을 통해 정점 i,j 간의 최단 거리를 구할 수는 있지만, 어떤 정점을 거치는지 경로를 알 수는 없습니다. 이를 위에서는 직전 정점 행렬(P)을 유지해야합니다. 직전 정점 행렬이란 i 정점에서 j 정점까지의 최단 경로에서 j 정점 직전에 위치하는 정점을 저장하는 행렬을 의미합니다.

 

초기 직전 정점 행렬은 다음과 같습니다.

직전 정점 행렬 P

인접 행렬을 갱신하면서 i,j의 정점사이에서 k를 거쳐 가는 경로가 최단 경로라면 P(i,j)를 k로 갱신해주면 모든 정점이 추가된 이후 최단 경로에 속하는 정점을 구할 수 있습니다. 자세한 내용은 이후 코드에 존재합니다.

---

Java 구현

자바로 구현한 알고리즘은 다음과 같습니다. Input은 백준 플로이드 문제와 동일하게 위의 그래프를 (start, destination, weight) 형태로 받는 상황으로 설정하였습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Blog {
	static final int INF = 99999;
	static final int NIL = -1;
	static int[][] D = new int[6][6];
	static int[][] P = new int[6][6];
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

	public static void main(String[] args) throws IOException {
		// Initialize
		for (int i = 0; i < 6; i++) {
			for (int j = 0; j < 6; j++) {
				P[i][j] = NIL;
				D[i][j] = INF;
			}
		}

		// process input
		for (int i = 0; i < 8; i++) {
			String[] line = br.readLine().split(" ");
			int start = Integer.parseInt(line[0]);
			int dest = Integer.parseInt(line[1]);
			int weight = Integer.parseInt(line[2]);
			D[start][dest] = weight;
			P[start][dest] = start;
		}
		floydWarshall();
	}

	public static void floydWarshall() {
		for (int k = 1; k <= 5; k++) {
			for (int i = 1; i <= 5; i++) {
				for (int j = 1; j <= 5; j++) {
					if (D[i][j] <=  D[i][k] + D[k][j]) continue;
					D[i][j] = D[i][k] + D[k][j];
					P[i][j] = k;
				}
			}
		}
	}
}

 

해당 코드를 통해 얻은 인접 행렬과 직전 정점 행렬은 다음과 같습니다.

Input
=================
1 2 3
1 4 4
2 3 7
2 5 5
4 2 2
4 5 2
5 1 1
5 3 3

Init
======= D ========
INF 3  INF 4  INF 
INF INF 7  INF 5  
INF INF INF INF INF 
INF 2  INF INF 2  
1  INF 3  INF INF 
======= P ========
-1 1  -1 1  -1 
-1 -1 2  -1 2  
-1 -1 -1 -1 -1 
-1 4  -1 -1 4  
5  -1 5  -1 -1 


Add :1
======= D ========
INF 3  INF 4  INF 
INF INF 7  INF 5  
INF INF INF INF INF 
INF 2  INF INF 2  
1  4  3  5  INF 
======= P ========
-1 1  -1 1  -1 
-1 -1 2  -1 2  
-1 -1 -1 -1 -1 
-1 4  -1 -1 4  
5  1  5  1  -1 


Add :2
======= D ========
INF 3  10  4  8  
INF INF 7  INF 5  
INF INF INF INF INF 
INF 2  9  INF 2  
1  4  3  5  9  
======= P ========
-1 1  2  1  2  
-1 -1 2  -1 2  
-1 -1 -1 -1 -1 
-1 4  2  -1 4  
5  1  5  1  2  


Add :3
======= D ========
INF 3  10  4  8  
INF INF 7  INF 5  
INF INF INF INF INF 
INF 2  9  INF 2  
1  4  3  5  9  
======= P ========
-1 1  2  1  2  
-1 -1 2  -1 2  
-1 -1 -1 -1 -1 
-1 4  2  -1 4  
5  1  5  1  2  


Add :4
======= D ========
INF 3  10  4  6  
INF INF 7  INF 5  
INF INF INF INF INF 
INF 2  9  INF 2  
1  4  3  5  7  
======= P ========
-1 1  2  1  4  
-1 -1 2  -1 2  
-1 -1 -1 -1 -1 
-1 4  2  -1 4  
5  1  5  1  4  


Add :5
======= D ========
7  3  9  4  6  
6  9  7  10  5  
INF INF INF INF INF 
3  2  5  7  2  
1  4  3  5  7  
======= P ========
5  1  5  1  4  
5  5  2  5  2  
-1 -1 -1 -1 -1 
5  4  5  5  4  
5  1  5  1  4

 

최단 경로에 해당하는 정점을 구하는 방법은 P[start][end]의 값(직전 정점)이 start와 같아질 때 까지 값을 찾아가는 방법을 통해 구할 수 있습니다.. 1 → 3을 예시를 들면 다음과 같습니다.

• P[1][3] = 5
• P[1][5] = 4
• P[1][4] = 1

이 때 최종 경로는 1 ⇒ 4 ⇒ 5 ⇒ 3이 됩니다. 해당 과정을 Java 코드로 나타내면 다음과 같습니다.

static void printPath(int start, int end) {
	Stack<Integer> path = new Stack<>();
	while(true) {
		path.add(end);
		if (P[start][end] == start) {
			path.add(start);
			break;
		}
		end = P[start][end];
	}
	while(!path.isEmpty()) 
		System.out.print(path.pop());
}