Graph/SingleSourceShortestPath/bellmanFord.cxx File Reference

BellmanFord implementation of Single Source Shortest Path

Contains BellmanFord implementation for solving Single Source Shortest Path problems. More...

#include "Graph.h"

Functions

void output (int n, vector< int > &dist, vector< int > &pred)
 Useful debugging method.
void singleSourceShortest (Graph const &graph, int s, vector< int > &dist, vector< int > &pred)
 Interface to single source Shortest Path problem.


Detailed Description

BellmanFord implementation of Single Source Shortest Path

Contains BellmanFord implementation for solving Single Source Shortest Path problems.

Author:
George Heineman
Date:
6/15/08

Function Documentation

void output ( int  n,
vector< int > &  dist,
vector< int > &  pred 
)

Useful debugging method.

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

Interface to single source Shortest Path problem.

Graph weights can be negative so long as there are no negative cycles.

Parameters:
graph the graph to be processed.
s the source vertex from which to compute all paths.
dist array to contain shortest distances to all other vertices.
pred array to contain previous vertices to be able to recompute paths.

Algorithm Development Kit 1.0