티스토리 뷰

알고리즘

[Graph] Floyd Warshall?

seunggabi 승가비 2018. 9. 8. 02:03

[Graph] Floyd Warshall?


최단 경로 계산할때 제일 간단한 알고리즘.

어려워 보이지만 쉽다.

최대값, 최소값 판단 기준을 커스터마이징 해야해서 조건을 잘 적고 하나씩 적용해야된다.


예제: https://www.acmicpc.net/problem/11404


// floyd warshall
// memset(arr, value, sizeof(arr) - <string.h>
// string s.front() s.back()
// time complexity: O(N^3)
// space complexity: O(N^2)

// 최대값
// 최소값; 비어있는 경우 !0 일때 삽입
// 제자리 못올때 i == j continue

#include <iostream>
#include <string.h>
using namespace std;

#define SIZE 100

int main() {
int size, cnt;
int map[SIZE][SIZE];
memset(map, 0, sizeof(map));

cin >> size >> cnt;

int start, end, cost;
for(int i=0; i<cnt; i++) {
cin >> start >> end >> cost;
if(!map[start-1][end-1] || map[start-1][end-1] > cost) {
map[start-1][end-1] = cost;
}
}

for(int k=0; k<size; k++) {
for(int i=0; i<size; i++) {
for(int j=0; j<size; j++) {
if(!map[i][k] || !map[k][j]) continue;
if(i == j) continue;

if(map[i][k]+map[k][j] < map[i][j] || !map[i][j]) {
map[i][j] = map[i][k]+map[k][j];
}
}
}
}

for(int i=0; i<size; i++) {
for(int j=0; j<size; j++) {
cout << map[i][j] << " ";
}
cout << endl;
}

return 0;
}


[출처] https://gist.github.com/zSANSANz/071012052e531dcaaec9b6f74b87d1c4

댓글
댓글쓰기 폼