최단 경로 ② ( Floyd - Warshall )

<본 게시글은 권오흠 교수님의 알고리즘 강의을 공부하고 정리한 글 입니다. >

 

 

지난 글에 이어서 all to all 최단 경로 알고리즘인  Floyd-warshall 알고리즘을 알아보자.

 

● 최단 경로
- 한 노드에서 다른 노드까지 이동하는데 드는 비용이 최소인 경로를 찾는 문제

1. Single - source ( one to all )  - Dijkstra 알고리즘, Bellman-Ford 알고리즘  - 하나의 출발 노드에서 모든 노드까지의 최단 경로를 찾는 문제.

2. Single - destination ( all to one ) - 사실상 one to all 이랑 같은 유형.
  - 모든 노드에서 하나의 목적 노드까지의 최단 경로를 찾는 문제.

3. Single - pair ( one to one )  - Dijkstra 알고리즘 으로 해결.
  - 주어진 한 노드에서 다른 한 목적 노드까지의 최단 경로를 찾는 문제.
  - 알려진 알고리즘 중에서 최악의 경우 시간복잡도가 one to all ( Dijkstra) 보다 나은 알고리즘이 없다.
    그래서 Dijkstra로 모든 노드 구하다 목적 노드 t가 나오면 search를 멈추는 방법으로 해결.

4. All - pair ( all to all ) - Floyd-warshall 알고리즘.
 - 모든 노드에서 모든 노드로 가는 최단 경로를 찾는 문제.

---

[ Floyd - Warshall ]

 

- Dijkstra 알고리즘과 여타 그래프 문제랑 마찬가지로 가중치 방향 그래프가 입력으로 주어진다.

   ( 허나 문제에 따라 graph를 그리지 않아도 될 때가 많다. 백준 11404 문제가 그러하다. ) 

- 이때, 모든 노드 쌍들간의 최단 경로의 길이를 구하는 문제이다.

- 다익스트라가 가장 적은 비용을 하나씩 선택했다면 플로이드는 '거쳐가는 정점'을 구해가면서 구한다.

- 전형적인 동적 계획법(DP) 전략에 기반한 알고리즘이다. 

- d(k) [ i, j ]  는

    - 중간 노드 집합 { 1,2,3,4 ... k } 에 속한 노드들만 거쳐서 노드 i 에서 j 까지 가는 최단 경로의 길이이다.

 

 

Floyd - Warshall 알고리즘

우리가 원하는 목표는 

 

d(n) [ i, j ] =  i 부터 j 까지 가는데 중간에 1 ~ n 의 속한 노드를 거쳐서 가는 최단 경로의 길이이다.

 

그렇다면 다이나믹 프로그래밍 답게 중간 단계인

 

d(k) [ i, j ] 에 대해서 생각해보자.

 

d(k) [ i, j ] = i 부터 j 까지 가는데 중간에 1 ~ k 사이에 속한 노드를 거쳐서 가는 경우인데, 이는 두 가지 경우가 있다.

 

- 노드 K를 지나지 않는 경우 : d(k-1) [ i , j ]  

- 노드 K를 지나는 경우 : d(k-1) [ i , k ] + d(k-1) [ k , j ]

 

노드 K를 지나지 않는 경우는 i 부터 j 까지 가는데 1 ~ k-1 사이에 속한 노드만을 거쳐서 간다는 소리이고

이는 d(k-1) [ i , j ]  이다.

 

노드 k를 지나는 경우는 i 부터 j 까지 가는데 1 ~ k 사이에 속한 노드만을 거쳐서 간다는 소리이고 그 중 K를 꼭 지나야하니깐 1 부터 k 까지 의 최단 경로인  d(k-1) [ i , k ]  와 k 부터 j까지 최단 경로인  d(k-1) [ k , j ] 의 합이다.

 

결국 d(k) [ i, j ] 는 노드 K를 지나지 않는 경우와 지나는 경우 둘 중에 작은 값이 된다.

min ( d(k-1) [ i , j ]  ,  d(k-1) [ i , k ] + d(k-1) [ k , j ] )

---

[ peseudo 코드 ]

 

위 알고리즘의 시간 복잡도는 자명하게 O(n^3) 이다.

 

그런데 시간 복잡도가 O(n^2) 인 Dijkstra 알고리즘을 모든 노드 N 에 대해서 실행하게 되면 All to All 이 되는데,

이는 이 경우에도 시간 복잡도가 O(n^3)  이다.

 

그런 의미에서 위 Floyd-Warshall 알고리즘은 자랑스러운것은 아니다.

 

또 한 가지,

 

위 수도 코드를 실제 구현할때는 k,i,j 를 d[k][i][j]의 3차원 배열로 해야하는데,

 

그렇지 않고아래 처럼 d[i][j]의 2차원 배열로 표현해도 충분하다.

 

 

 

이유  : d(k)[ i, k ] 는 d(k-1)[ i, k ] 랑 같기 때문에 그대로 덮어 씌어도 된다.

 

이 부분은 아래의 강의를 참조하는게 이해하는데 쉬울것 같다.

https://www.youtube.com/watch?v=5uqOvsVmfJw&list=PL52K_8WQO5oUuH06MLOrah4h05TZ4n38l&index=40

---

[ 구현 ] 

 

우리의 목표는 d(n)[i,j] 를 구하는 것이다.

 

 

1. 초기화

 - d[i,j] 를 초기화 해준다. ( i 랑 j 가 같으면 0 으로 아니라면 INF 로)

 

for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= n; j++) {
		if (i == j)dist[i][j] = 0;
		else { dist[i][j] = INF; }
	}
}

 

2. 그래프 입력을 받으면서 서로 연결된 노드가 있다면 거리를 업데이트 해준다.

※ 주의 할 점은 문제에서 같은 노드를 연결하는  동일한 엣지를 다른 비용으로 하나 이상 줄 수도 있다.

    이 경우, 가장 작은 값을 dist[i][j] 로 해야한다.    --> 백준 11404 문제가 그러하다.

 

while (m--) {
	int a, b, c;
	cin >> a >> b >> c;
	graph[a].push_back({ b,c });
	dist[a][b] = std::min(dist[a][b], c);
}

 

3. 플로이드 와샬 알고리즘을 사용한다.

 

void floyd() {
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				
				dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j]);
			}
		}
	}

}

 

---

 

[ 경로 출력 ]

 

중간 k 값을 2차원 배열에 저장하여 

recursion 으로 앞에서부터 하나씩 출력해주면 된다.

 

---

ref :: https://www.youtube.com/watch?v=5uqOvsVmfJw&list=PL52K_8WQO5oUuH06MLOrah4h05TZ4n38l&index=40