Graph/SingleSourceShortestPath/singleSourceShortest.h File Reference

Defines the Single Pair Shortest Path Problem interface. More...

#include "Graph.h"

Go to the source code of this file.

Functions

void singleSourceShortest (Graph const &g, int s, vector< int > &dist, vector< int > &pred)
 Interface to single source Shortest Path problem.
void singleSourceShortestDense (int n, int **const weight, int s, int *dist, int *pred)
 Interface to dense version of single source Shortest Path problem.


Detailed Description

Defines the Single Pair Shortest Path Problem interface.

Can be implemented by a variety of implementations, including Dijkstra's algorithm.

Author:
George Heineman
Date:
6/15/08

Function Documentation

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

Interface to single source Shortest Path problem.

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

void singleSourceShortestDense ( int  n,
int **const   weight,
int  s,
int *  dist,
int *  pred 
)

Interface to dense version of single source Shortest Path problem.

An edge weight of INF means no edge. Suitable for Dense Graphs Only.

Parameters:
n number of vertices in graph
weight two-dimensional array of edge weights (INF means no edge).
s the source vertex from which to compute all paths.
dist computed dist[] array to all other vertices.
pred computed pred[]array to contain back references for paths.

Algorithm Development Kit 1.0