Ⅰ. Floyd Warshall 알고리즘은 '모든 정점'에서 '모든 정점'으로의 최단 경로를 구하는 알고리즘이다.
Ⅱ. Dijkstra 알괴즘은 가장 적은 비용을 하나씩 선택했다면, Floyd Warshall 알고리즘은 '거쳐가는 정점' 을 기준으로 알 고리즘을 수행한다.
위 테이블은 '현재까지 계산된 최소 비용' 이다.
예를들어, 노드 1을 거쳐가는 경우 대각선과 1이 포함된( (1,n), (n,1) )을 제외한 부분을 갱신시키면 된다.
다시말해 x -> y 로 가는 최소비용과 X -> 1 -> Y로 가는 비용을 비교하여 더 작은 값으로 갱신시킨다.
ex) D[2,3] vs D[2,1] + D[1,3]
위와 같은 방법으로 2를 거쳐가는 경우, 3을 거쳐가는 경우등을 계산하면 된다.
n을 입력받아 n x n 배열을 생성하고, 각각 좌표에 맞는 값을 입력 받았다.
#include <iostream>
#include <stdlib.h>
using namespace std;
int n; // n x n 배열 생성
int** arr; // 배열
void floydWarshall() {
for (int i = 0; i < n; i++) // 거쳐가는 노드 i
for (int j = 0; j < n; j++) // 출발 노드 j
for (int k = 0; k < n; k++) // 도착 노드 k
if (arr[j][k] > arr[j][i] + arr[i][k]) // j -> k 보다 j -> i -> k가 더 cost가 적다면
arr[j][k] = arr[j][i] + arr[i][k];
}
int main() {
cin >> n;
arr = (int**) new int[n]; // n개의 행 생성
for (int i = 0; i < n; i++) { // n개의 열 생성
arr[i] = new int[n];
}
for (int i = 0; i < n; i++) // 입력
for (int j = 0; j < n; j++)
cin >> arr[i][j];
/* 입력값 예시
0 5 100001 8
7 0 9 100001
2 100001 0 4
100001 100001 3 0
*/
floydWarshall();
cout << endl; // 출력
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << arr[i][j] << ' ';
}
cout << endl;
}
for (int i = 0; i < n; i++) { // 메모리 해제
delete arr[i];
} delete arr;
return 0;
}
Floyd Warshall 알고리즘이 Dijkstra 알고리즘보다 구현 하기는 쉽지만 시간 복잡도가 O(N^3)이다.
반면 Djkstra 알고리즘은 우선순위 큐를 사용할 경우 O(NlogN) 이다.
'Algorithm' 카테고리의 다른 글
Bipartite Match [c++] (0) | 2021.01.27 |
---|---|
Topology Sort [c++] (0) | 2021.01.21 |
Dijkstra [c++] (0) | 2021.01.15 |
소수(Prime Number) 판별 [c++] (0) | 2021.01.13 |
Binary Tree & Traversal [c++] (0) | 2021.01.11 |