Contains the Floyd-Warshall implementation which solves the All Pairs Shortest Path problem. More...
#include <iostream>
#include "Graph.h"
Functions | |
| void | debug (vector< vector< int > > &dist, vector< vector< int > > &pred) |
| Useful debugging method to show dist,pred values. | |
| void | allPairsShortest (Graph const &graph, vector< vector< int > > &dist, vector< vector< int > > &pred) |
| interface to all-pairs shortest path | |
| void | constructShortestPath (int s, int t, vector< vector< int > > const &pred, list< int > &path) |
| interface to compute shortest path between <s,t>. | |
Contains the Floyd-Warshall implementation which solves the All Pairs Shortest Path problem.
Operates over
| void allPairsShortest | ( | Graph const & | graph, | |
| vector< vector< int > > & | dist, | |||
| vector< vector< int > > & | pred | |||
| ) |
interface to all-pairs shortest path
| graph | contains the graph instance | |
| dist | output dist[][] array for shortest distance from each vertex | |
| pred | output pred[][] array to be able to recompute shortest paths |
| void constructShortestPath | ( | int | s, | |
| int | t, | |||
| vector< vector< int > > const & | pred, | |||
| list< int > & | path | |||
| ) |
interface to compute shortest path between <s,t>.
Note that s and t must be valid integer vertex identifiers. If no path is found between s and t, then an empty path is returned.
| s | desired source vertex | |
| t | desired target vertex | |
| pred | output pred[][] array computed by allPairsShortest. | |
| path | list which contains the path, should it exist. |
| void debug | ( | vector< vector< int > > & | dist, | |
| vector< vector< int > > & | pred | |||
| ) |
Useful debugging method to show dist,pred values.
Also used to generate useful figures for the execution of the algorithm.
| dist | output dist[][] array for shortest distance from each vertex | |
| pred | output pred[][] array to be able to recompute shortest paths |
Algorithm Development Kit 1.0