Graph/AllPairsShortestPath/allPairsShortest.h File Reference

Defines the All Pairs Shortest Problem interface. More...

#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>.


Detailed Description

Defines the All Pairs Shortest Problem interface.

Can be implemented by a variety of implementations, including Floyd Warshall

Author:
George Heineman
Date:
6/15/08

Function Documentation

void allPairsShortest ( Graph const &  graph,
vector< vector< int > > &  dist,
vector< vector< int > > &  pred 
)

interface to all-pairs shortest path

Parameters:
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.

Parameters:
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