[Graph] Floyd Warshall?

[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