[그래프]Floyd-Warshall

Floyd-Warshall

모든 정점에서부터 서로 다른 모든 정점들간의 최단 거리를 구하는 알고리즘

dijikstra는 한 정점에서 다른 모든 정점으로 가는 최단 거리

음수 가중치를 갖는 간선도 순환만 없다면 처리할 수 있음

• 중요한 점은 플로이드 와샬은 한 정점에서 출발해서 출발한 정점으로 다시 돌아오는 거리까지 계산한다.
  문제에 따라 다르게 활용되니 알아두면 좋을 것 같다.

시간복잡도

O(n^3)

예시 코드

바깥쪽 반복문(k) : 중간에 거쳐가는 정점
중간 반복문(i) : 출발하는 정점
안쪽 반복문(j) : 도착하는 정점
이미 계산해놓은 출발지에서 도착지로 가는 길보다 중간에 거쳐가는 정점을 통해 가는 길이 더 짧다면 갱신

const int INF = 0x7fffffff;

int matrix[4][4] = {
  { 0, 1, 3, 8 },
  { 7, 0, INF, INF },
  { 2, 2, 4, 4 },
  { 8, INF, 5, INF }
};

void floydWarshall(){
    for(int k = 0; k < 4; k++)  // k 는 거쳐가는 정점
      for(int i = 0; i < 4; i++)  // i 는 행 (출발 정점)
        for(int j = 0; j < 4; j++)  // j 는 열 (도착 정점)
          if (matrix[i][k] + matrix[k][j] < matrix[i][j])  // 점화식 distance[i,j] = min(distance[i,j], distance[i,n] + distance[n,j])
             matrix[i][j] = matrix[i][k] + matrix[k][j];
}