## All Pair Shortest Path (APSP)

**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

- find the shortest path
- we can use another matrix called predecessor matrix to construct the shortest path.

- 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.

- 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

I hear that this only works for weighted graphs, do you know of an implementation of a similar algorithm to unweighted undirected graphs?

siriusJanuary 29, 2013 at 9:33 PM