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