플로이드 워셜 알고리즘 c++
이전 글에서 살펴본 다익스트라 알고리즘은 한 정점에서 다른 정점으로 가는 최단거리를 구할때 사용한다. 하지만 A -> B 의 최단경로만 구할 수 있다는 점과, 비용이 음수일 경우 하지 못한다는 단점이 있었다.
플로이드 워셜 알고리즘은 음수일때도 작동하며 모든 정점들 사이의 최단 거리를 한꺼번에 계산할 수 있다는 것이 장점이다.
하지만 그만큼 시간복잡도가 크기 때문에 하나의 거리만 구할때는 굳이? 이다.
모든 경로를 계산해서 모든 쌍의 최단 경로를 계산할 수 있는 알고리즘이다.
그렇기 때문에 사실상 좀 한정적인 알고리즘인 것 같긴 하다
모든 경로를 출력하라고 하거나 모든 비용을 알아야 풀 수 있는 문제가 나오면 사용하면 될 듯 하다.
플로이드 워셜은 3중 반복문을 이용해서 구하게 되는데 그만큼 시간복잡도는 극악을 달린다.
이 알고리즘의 중점은 ‘경유지’를 기준으로 거리들을 계산한다는 점인데
a, b, c, d 노드가 있을 때 경유지를 a라고 잡는다면 b -> a -> c, b -> a -> d, c -> a -> d 와 같이 a를 경유해서 갈 수 있는 모든 경우의 수를 따져서 테이블을 업데이트 시키면 된다.
거의 브루트 포스와 같은 방법으로 계산하는 것이기 때문에 음수가 있어도 상관이 없으며 무엇보다 확실하긴 하다.
의 방법으로 작동하게 된다.
이전 다익스트라 알고리즘에서는 하나의 노드에서 시작하기 때문에 1차원 배열으로도 구현할 수 있었지만
플로이드 워셜 알고리즘은 모든 노드에 대한 모든 경우를 찾아야 하기 때문에 2차원 배열로 구현해야 한다.
위와 같은 그래프가 있다고 가정해보자
편의를 위해서 양방향 그래프로 설정해 두었지만 실제 플로이드 워셜은 단방향 그래프에서도 정상적으로 작동한다.
네개의 노드가 존재하기 때문에 2차원 행렬을 아래와 같이 초기화 시켜준다.
| 0번 | 1번 | 2번 | 3번 | |
| 0번 | 0 | 1 | 1 | INF |
| 1번 | 1 | 0 | 2 | 3 |
| 2번 | 1 | 2 | 0 | INF |
| 3번 | INF | 3 | INF | 0 |
위 간선에 있는 데이터들을 업데이트 시켜주었다.
위의 INF들은 직접적으로 연결된 간선이 없어 아직 도달하지 못하는 부분이다.
제일 처음에 경유지로 할 노드를 0번 노드로 정해준다.
그러면 모든 노드들의 경로에 0번 노드를 경유해서 가는 비용을 계산해준다.
1 -> 0 -> 2 비용 1 + 1 = 2
1 -> 0 -> 3 비용 1 + INF = INF
2 -> 0 -> 3 비용 2+INF = INF
3 -> 0 -> 1 비용 INF
3 -> 0 -> 2 비용 INF
모든 경우가 모두 현재 테이블에 있는 비용보다 작지 않으므로 업데이트 하지 않는다.
| 0번 | 1번 | 2번 | 3번 | |
| 0번 | 0 | 1 | 1 | INF |
| 1번 | 1 | 0 | 2 | 3 |
| 2번 | 1 | 2 | 0 | INF |
| 3번 | INF | 3 | INF | 0 |
두번째로 경유할 노드는 1번 노드이다.
0 -> 1 -> 2 비용 1 + 2 = 3
0 -> 1 -> 3 비용 1 + 3 = 4
2 -> 1 -> 3 비용 2 + 3 = 5
3 -> 1 -> 0 비용 3 + 1 = 4
3 -> 1 -> 2 비용 3 + 2 = 5
0번 -> 3번으로 가는 비용, 2번 -> 3번으로 가는 비용이 원래 테이블에 있는 INF보다 작으므로 각각 4, 5로 업데이트 한다.
또한 3번 -> 0번, 3번 -> 2번 비용도 각각 INF에서 4, 5로 업데이트 한다
| 0번 | 1번 | 2번 | 3번 | |
| 0번 | 0 | 1 | 1 | 4 |
| 1번 | 1 | 0 | 2 | 3 |
| 2번 | 1 | 2 | 0 | 5 |
| 3번 | 4 | 3 | 5 | 0 |
세번째로 경유할 노드는 2번노드이다.
0 -> 2 -> 1 비용 3
0 -> 2 -> 3 비용 1 + 5 = 6
1 -> 2 -> 0 비용 2 + 1 = 3
1 -> 2 -> 3 비용 2 + 5 = 7
3 -> 2 -> 0 비용 5 + 1 = 6
3 -> 2 -> 1 비용 5 + 2 = 7
모든 경우의 수가 현재 테이블에 있는 것보다 크기 때문에 업데이트 하지 않는다.
| 0번 | 1번 | 2번 | 3번 | |
| 0번 | 0 | 1 | 1 | 4 |
| 1번 | 1 | 0 | 2 | 3 |
| 2번 | 1 | 2 | 0 | 5 |
| 3번 | 4 | 3 | 5 | 0 |
마지막으로 경유할 노드는 3번 노드이다.
위와 같이 계산해주게 되면 모든 값을 업데이트 할 수 없다.
그래서 최종적으로 모든 노드들의 비용은 아래와 같게 된다.
| 0번 | 1번 | 2번 | 3번 | |
| 0번 | 0 | 1 | 1 | 4 |
| 1번 | 1 | 0 | 2 | 3 |
| 2번 | 1 | 2 | 0 | 5 |
| 3번 | 4 | 3 | 5 | 0 |
이로써 모든 노드들의 최단 경로를 구하게 되었다.
위의 가장 간단한 예제인 4개의 노드를 이용한 것에서도 수많은 연산을 진행하였다.
그만큼 시간복잡도 높지만 모든 정점의 모든 정점까지의 최단 경로를 구할 수 있다는 점이 큰 장점이다.
당연하게도 모든 쌍을 구해야 할때는 플로이드 워셜만큼 좋은게 없고, 음수의 비용을 가질 경우 다익스트라를 사용하지 못하기 때문에 사용하게 될 경우가 생길 수 도 있다.
노드 수가 V일때
O(V^3)
vector<vector<int>> floydWarshall(vector<vector<int>>& graph, int V) {
// 거리 정보를 담을 행렬 dist 초기화
vector<vector<int>> dist(V, vector<int>(V, INF));
// 초기 거리를 그래프의 가중치로 설정
for (int i = 0; i < V; ++i) {
for (int j = 0; j < V; ++j) {
dist[i][j] = graph[i][j];
}
// 자기 자신으로의 거리는 0
dist[i][i] = 0;
}
// 플로이드 워셜 알고리즘 실행
for (int k = 0; k < V; ++k) { // 경유지
for (int i = 0; i < V; ++i) { // 출발지
for (int j = 0; j < V; ++j) { // 목적지
// i에서 j로 가는 거리와 k를 거쳐 가는 거리 비교 및 갱신
if (dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
return dist;
} 코드는 크게 어려운 것 없이 간단한데
제일 먼저 dist라는 2차원 배열을 초기화 시켜주고, 자신의 거리는 0으로 설정하고 간선의 길이도 설정해 준다.
플로이드 워셜 알고리즘은 위와 같은 3중배열로 실시하게 되는데
첫번째 for문은 경유지를 바꾸는 반복문이고
두번째 for문은 출발지, 세번째 for문은 목적지를 선택함으로써
모든 경우에 대한 비용을 계산해서 dist를 업데이트 하게 된다.
비전공자도 배울 수 있는 타입스크립트 자바스크립트는 이상하게 정이안가는 언어중에 하나이다. 분명 web을 처음 시작했을 때…
IT 엔지니어를 위한 AWS 운영의 기본과 노하우 선택한 이유 AWS는 정말 공부해야지 공부해야지... 하면서도 쉽게…
개발하는 남자의 핸즈온 플러터 최근 계속해서 플러터를 개발할 일들이 많은데, 워낙 가지고 있는 강의들은 많은데…
갑자기 독스헌트 사업계획서? 아직 거창한 사업계획서를 쓸일은 없지만, 최근 진행하는 프로젝트의 지원금을 받을 수 있을까…