Floyd's Algorithm

Explain

• Floyd-Warshall algorithm 또는 Floyd's algorithm 이라고 불리우며 negative cycles을 가지지 않은 weighted graph에서 임의의 두 vertex 사이의 최단 거리를 구하는 알고리즘이며 \(\Theta(n^3) \) 의 시간복잡도를 나타내며 optimal algorithm의 한 종류이다.

Notation

• \(N :\) vertex 의 개수
• \(W :\) 인접 vertex 간의 weight \( |N^2| \) 이며 인접하지 않은 vertex 간의 거리는 \(\infty\)
• \( D_{(k)}[i,j] = \) from i to j 의 경로중 k 이하의 vertex만을 통과하여 얻을 수 있는 최단거리
• \( D_{(0)}[i,j] = W[i,j] \) 0이하의 vertex만을 통과하여 i,j를 지나는 경로는 해당 edge의 weight이다.

Algorithm

• \( D_{(0)}[i,j] = W[i,j] \) 를 활용하여 \( D_{(0)}[1...N,1...N] \)을 구할 수 있으며

• 이후, \( D_{(1)}[i,j] \) 의 경우를 생각해보면
• \(i \rightarrow j\) , \(i \rightarrow 1 \rightarrow j\)
• 위 2가지 경우로 나눌수 있으며 그러므로
• \( D_{(1)}[i,j] = \min(D_{(0)}[i,j], D_{(0)}[i,0] + D_{(0)}[0,j])\) 이다. 

$$\text{thus,} D_{(k)}[i,j] = \min(D_{(k-1)}[i,j],D_{(k-1)}[i,k] + D_{k-1}[k,j])$$

• 즉, \(D_{(k-1)}\) 을 구하면 \(D_{k}\) 를 구할 수 있다.

Code_only shortest distance

//Floyd's algorithm

#include <stdio.h>

#define MAX 5
#define INF 99999

int min(int x,int y);
void floyds(int n,int W[][MAX]);
void display(int n, int D[][MAX]);

int main(void)
{
	// 두 vertex간의 거리 
	int W [MAX][MAX] = {
		{0,1,INF,1,5},
		{9,0,3,2,INF},
		{INF,INF,0,4,INF},
		{INF,INF,2,0,3},
		{3,INF,INF,INF,0}
	};

	int D[MAX][MAX];

	floyds(5,W,D);
}

void display(int n,int D[][MAX])
{
	int i,j;

	for(i=0;i<n;++i)
	{
		for(j=0;j<n;++j)
		{
			if(D[i][j] == INF)
				printf("%5s","INF");
			else
				printf("%5d", D[i][j]);
		}
		puts("");
	}
}

void floyds(int n, int W[][MAX], int D[][MAX])
{
	int k,i,j,l;

	D=W; 

	for(k=0;k<n;++k)
	{
		for(l=0;l<n;++l)
		{
			D[k][l] = W[k][l];
			D[l][k] = W[l][k];
		}

		for(i=0;i<n;++i)
		{
			if(i==k){
				continue;
			}

			for(j=0;j<n;++j)
			{
				if(j==k) continue; 
				if(i==j) continue; 
				
				D[i][j] = min(D[i][j], D[i][k] + D[k][j]); 
			}
		}
	}
	display(5,D);
}

int min(int x,int y)
{
	if(x>y) return y;
	return x;
}

Code_distance with shortest path.

\(P[i,j] = D[i,j]\)의 intermediate point 라고 했을때,

$$\text{if    }D_{(k-1)}[i,j] > D_{(k-1)}[i,k] + D_{(k-1)[k,j]} $$

위 조건문이 성립하는경우 최단 경로는 \(i\rightarrow k \rightarrow j\) 이므로 \(P[i,j] = k\) 이다.

//Floyd's algorithm
#include <stdio.h>

#define MAX 5
#define INF 99999

int min(int x,int y);
void floyds(int n,int W[][MAX], int D[][MAX]);
void display(int n, int D[][MAX]);
void print_path(int start, int end, int P[][MAX]);

int main(void)
{
	// 두 vertex간의 거리 
	int W [MAX][MAX] = {
		{0,1,INF,1,5},
		{9,0,3,2,INF},
		{INF,INF,0,4,INF},
		{INF,INF,2,0,3},
		{3,INF,INF,INF,0}
	};

	int D[MAX][MAX];

	floyds(5,W,D);
}

void display(int n,int D[][MAX])
{
	int i,j;

	for(i=0;i<n;++i)
	{
		for(j=0;j<n;++j)
		{
			if(D[i][j] == INF)
				printf("%5s","INF");
			else
				printf("%5d", D[i][j]);
		}
		puts("");
	}
}

void floyds(int n, int W[][MAX], int D[][MAX])
{
	int k,i,j,l;
	int P[MAX][MAX] = {0};

	D=W; 

	for(k=0;k<n;++k)
	{
		for(l=0;l<n;++l)
		{
			D[k][l] = W[k][l];
			D[l][k] = W[l][k];
		}

		for(i=0;i<n;++i)
		{
			if(i==k){
				continue;
			}

			for(j=0;j<n;++j)
			{
				if(j==k) continue; 
				if(i==j) continue; 
				
				if(D[i][j] > D[i][k] + D[k][j])
				{
					P[i][j] = k;
					D[i][j] = D[i][k] + D[k][j];
				}
			}
		}
	}

	printf("shortest path from 1 to 0\n");
	printf("%d->",1);
	print_path(1,0,P);
	printf("%d\n",0);
}


void print_path(int start, int end, int P[][MAX])
{
	if(P[start][end] != 0)
	{
		print_path(start, P[start][end], P);
		printf("%d->",P[start][end]);
		print_path(P[start][end], end, P);
	}
}

int min(int x,int y)
{
	if(x>y) return y;
	return x;
}

Reference

• Wiki - Floyd-Warshall algorithm