Posts Tagged ‘pair’
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