COME ON CODE ON

A blog about programming and more programming.

Posts Tagged ‘all

All Pair Shortest Path (APSP)

with one comment

Question : Find shortest paths between all pairs of vertices in a graph.

Floyd-Warshall Algorithm
It is one of the easiest algorithms, and just involves simple dynamic programming. The algorithm can be read from this wikipedia page.

#define SIZE 31
#define INF 1e8
double dis[SIZE][SIZE];
void init(int N)
{
	for (k=0;k<N;k++)
		for (i=0;i<N;i++)
			dis[i][j]=INF;
}
void floyd_warshall(int N)
{
        int i,j,k;
        for (k=0;k<N;k++)
                for (i=0;i<N;i++)
                        for (j=0;j<N;j++)
                                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}

int main()
{
	//input size N
	init(N);
	//set values for dis[i][j]
	floyd_warshall(N);
}

We can also use the algorithm to

  1. find the shortest path
    • we can use another matrix called predecessor matrix to construct the shortest path.
  2. find negative cycles in a graph.
    • If the value of any of the diagonal elements is less than zero after calling the floyd-warshall algorithm then there is a negative cycle in the graph.
  3. find transitive closure
    • to find if there is a path between two vertices we can use a boolean matrix and use and-& and or-| operators in the floyd_warshall algorithm.
    • to find the number of paths between any two vertices we can use a similar algorithm.

NJOY!!
-fR0DDY

Advertisements

Written by fR0DDY

August 7, 2010 at 1:53 PM

%d bloggers like this: