플로이드 워셜 알고리즘

플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘이다.

시간복잡도는 $O(V^3)$이다. 다익스트라 알고리즘과는 달리 모든 노드 쌍에 대해 최단 거리를 구하고, 음의 가중치를 가지는 그래프에서도 쓸 수 있다는 것이 특징.

플로이드-워셜 알고리즘은 임의의 노드 s에서 e까지 가는 데 걸리는 최단거리를 구하기 위해, s와 e 사이의 노드인 m에 대해 s와 m까지 가는 데 걸리는 최단거리와 e와 m까지 가는 데 걸리는 최단거리를 이용한다.

s : 시작 노드

e : 목표 노드

m : s와 e 사이의 노드

알고리즘

void Floyd_Warshall() {
  for(m=1; m<=N; m++)
    for(s=1; s<=N; s++)
      for(e=1; e<=N; e++)
         d[s][e]=d[s][e] > d[s][m] + d[m][e] ? d[s][m]+d[m][e] : d[s][e];
}

구현 코드

#include <stdio.h>
#define INF 1<<20
 
int d[1000][1000];
int n, m;
 
void Init()
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if(i!=j) d[i][j] = INF; 
}
 
void Floyd()
{
    for (int m = 1; m <= n; m++) //가운데 노드
        for (int s = 1; s <= n; s++) //시작 노드
            for (int e = 1; e <= n; e++) //마지막 노드
                if (d[s][e] > d[s][m] + d[m][e])
                    d[s][e] = d[s][m] + d[m][e]; //가운데를 거쳐가는 것이 더 빠르면 그걸로 업데이트한다.
}
 
int main()
{
    scanf("%d %d", &n, &m); //n: 노드의 개수, m: 간선의 개수
    Init(); //d의 모든 값을 무한으로 초기화(단, d[i][i]는 0)
    for (int i = 0; i < m; i++) { //인접행렬 입력받기
        int x, y, c;
        scanf("%d %d %d", &x, &y, &c);
        d[x][y] = c;
    }
 
    Floyd();
 
    for (int i = 1; i <= n; i++) //모든 경로의 최단거리 출력
        for(int j=1; j<=n; j++)
            printf("Shortest dist from %d to %d: %d\n", i, j, d[i][j]);