플로이드-워셜 알고리즘

1. 개요[편집]

---

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

시간복잡도는 <math>O(V^3)</math>이다. 다익스트라 알고리즘과는 달리 모든 노드 쌍에 대해 최단 거리를 구하고, 음의 가중치를 가지는 그래프에서도 쓸 수 있다는 것이 특징이다. 플로이드와 워셜이 개발하였으며, 이 중 플로이드는 공로를 인정받아 튜링상을 받았다.[1][2]

2. 설명[편집]

---

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

조금 더 구체적인 설명을 위해, 임의의 노드 s 부터 e 까지 가는데 걸리는 최단거리를

d[s][e]

라고 하자. (처음에

d[s][e]

의 값은 노드 s와 노드 e가 직접적으로 연결되어 있다면 그 노드의 가중치만큼, 그렇지 않다면 무한(INF)로 초기화한다.[3]) 이

d[s][e]

를 구하기 위해서, s와 e 사이의 모든 노드 m에 대해, 현재

d[s][e]

에 저장되어 있는 값과,

d[s][m]+d[m][e]

의 값을 비교한다. 이 때

d[s][m]+d[m][e]

의 값이 현재의

d[s][e]

값보다 작으면,

d[s][e]

를

d[s][m]+d[m][e]

의 값으로 업데이트한다.

2.1. 코드[편집]

---

단순히 반복문을 3번 중첩시키기만 하면 되기 때문에 큰 어려움 없이 간결하게 구현할 수 있다. 단, 유의하여야 할 점은 for문에서 가운데 노드(m)가 제일 위에 있어야 한다는 점이다.

C언어로 구현한 플로이드-워셜 알고리즘은 다음과 같다.(C++)

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

다음 프로그램은 플로이드-워셜 알고리즘을 사용하여 그래프를 인접 행렬 형태로 입력받아 임의의 노드로부터 임의의 노드까지 가는 최단거리를 구해준다.

//Floyd calculates shortest dist from all nodes to all nodes

/*
0. Initialize d with inf except adj nodes
1. Find d[s][e] by comparing current d[s][e] with d[s][m]+d[m][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]);
}