#include "Graph.h"
Go to the source code of this file.
Functions | |
| 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>. | |
Can be implemented by a variety of implementations, including Floyd Warshall
| 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. |
Algorithm Development Kit 1.0