FloydWarshall Algorithm
목적
APSP를 위해 사용된다.
APSP는 All-Pairs Shortest Paths라는 뜻으로, 모든 vertex간 최단 거리를 구할 때 사용한다.
BellmanFord로도 source를 모든 vertex로 바꿔가며 찾을 수 있지만, FloydWarshall은 한 번에 모두 찾을 수 있다.
알고리즘 설명
핵심은 지나가는 vertex이다. source에서 destination까지 가는 path에 사용되는 vertex를 구별하며 알고리즘이 진행된다.
기본적인 알고리즘 구조이다.
A[k,i,j]라는 3차원 배열을 사용한다. 각각 edge에서 최대 number vertex/source/destination이다.
앞서 vertex에 numbering을 한다고 말했다. 예를 들어 k=3인 경우를 생각하자. 이 말은 source to vertex에서, 그 사이 vertex의 최대 number가 3이라는 것이다.
s-3-2-d는 되지만, s-4-1-3-2-d는 안된다는 것이다.
1) A[0,i,j]를 초기 설정한다. 만약 i=j라면 거리는 0, i,j가 한 edge의 끝점이라면 l_ij, 이 외에는 모두 +무한으로 둔다.
2) A[k,i,j]에 대해, 한 k에 대해 i to j(모든 vertex 간) 값을 구해야 한다.
A[k-1,i,j]와 A[k-1,i,k]+A[k-1,k,j] 중 최솟값을 업데이트 한다.
첫번째는 k-1인 경우가 그대로 최소인 경우이고, 두번째는 i..(k-1)..j보다 i..(k-1)..k ..(k-1)..j가 더 최소인 경우이다. 즉, k-1에서 k로 바뀌었을때 최단거리가 k를 지나는 경우이다.
3) 이 과정을 k를 1에서 n까지 바꿔가며 반복한다.
한 단계별로 O(1)이 걸리며, 총 O(V^3)의 시간 복잡도를 가지고 있다.
Negative cycle 체크
Negative cycle 체크하는 방법은 간단하다. 모든 vertex i에 대해 A[n,i,i]가 하나라도 음수면 negative cycle이 존재하는 것이다.
그 이유는 A[n, i, i]는 자신까지 가는 거리이므로 0이어야 한다. 그러나, 음수가 존재한다는 말은, 자기 자신까지의 거리가 0보다 짧아진다는 것으로, negative cycle을 돌았다는 의미이다.(초기 설정에 반함)
따라서 마지막에 이를 추가하면 negative cycle까지 체크할 수 있다.
FloydWarshall Algorithm 구현
//FloydWarshall function, input is vertex, edge number, graph and option
void FloydWarshall(int V, int E, int **graph, int option)
{
int **d = malloc(sizeof(int *)*(V+1)); // make distance array
for(int i=1; i<=V; i++)
{
d[i]=malloc(sizeof(int)*(V+1));
}
for(int i=1; i<=V; i++)
{
for(int j=1; j<=V; j++)
{
d[i][j]=graph[i][j]; // move graph's component
}
}
int **between = malloc(sizeof(int *)*(V+1)); // make between array, to find out the path
for(int i=1; i<=V; i++)
{
between[i]=malloc(sizeof(int)*(V+1));
}
for(int i=1; i<=V; i++)
{
for(int j=1; j<=V; j++)
{
if(graph[i][j]!=INT_MAX)
{
between[i][j]=-1; // they are neighbor
}
else
{
between[i][j]=0; // not connected
}
}
}
// Algorithm in lecture
for(int k=1; k<=V; k++)
{
for(int i=1; i<=V; i++)
{
for(int j=1; j<=V; j++)
{
if(d[i][k]!=INT_MAX && d[k][j]!=INT_MAX) // if one of them exceed, it makes - value (wrong)
{
if(d[i][j]>(d[i][k]+d[k][j])) // if it is small
{
d[i][j]=d[i][k]+d[k][j]; // update
between[i][j]=k; // make between node
}
}
}
}
}
for(int i=1; i<=V; i++)
{
if(d[i][i]<0)
{
negativeCycle=1; // check if A[i][i]<0 at n.
return;
}
}
if(negativeCycle!=1) // not negative
{
if(option != -1) // if option exists
{
for(int i=1; i<=V; i++)
{
if(d[option][i]!=INT_MAX)
{
printf("%d %d length: %d path:", option, i, d[option][i]); // just print option line
printf(" %d", option);
print_array(option, i, between);
printf("\n");
}
else
{
printf("%d %d length: inf path: none\n", option, i); // if no path
}
}
}
else // to print all vertex
{
for(int i=1; i<=V; i++)
{
for(int j=1; j<=V; j++)
{
if(i!=j)
{
if(d[i][j]!=INT_MAX) // if d is not inf
{
printf("%d %d length: %d path:", i, j, d[i][j]); // print path
printf(" %d", i);
print_array(i, j, between);
printf("\n");
}
else
{
printf("%d %d length: inf path: none\n", i, j); // else, print inf
}
}
}
}
}
}
}BellmanFord와 마찬가지로 구현 자체는 단순하지만 path 저장을 위해 복잡해진 것이다.
