Algorithm

Floyd Warshall [c++]

PON_Z 2021. 1. 19. 15:24

Ⅰ. 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]

 

1을 거쳐서 가는 경우의 최소비용

 위와 같은 방법으로 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) 이다.

 

 

728x90

'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