#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