Graph::ShortestPathProblem< Node, Edge > Class Template Reference

Single-source shortest paths (Dijkstra's algorithm) More...

#include <ShortestPaths.h>

Public Member Functions
	ShortestPathProblem (const Graph< Node, Edge > &g)
void	InitializeSource (int s)
void	InitializeSources (const vector< int > &s)
template<typename WeightFunc , typename Iterator >
void	FindPath (int t, WeightFunc w, Iterator it)
template<typename WeightFunc , typename Iterator >
int	FindAPath (const set< int > &t, WeightFunc w, Iterator it)
template<typename WeightFunc , typename Iterator >
void	FindAllPaths (WeightFunc w, Iterator it)
template<typename WeightFunc , typename InIterator , typename OutIterator >
void	IncreaseUpdate (int u, int v, WeightFunc w, InIterator in, OutIterator out)
template<typename WeightFunc , typename InIterator , typename OutIterator >
void	DecreaseUpdate (int u, int v, WeightFunc w, InIterator in, OutIterator out)
template<typename WeightFunc , typename InIterator , typename OutIterator >
void	DeleteUpdate (int u, int v, WeightFunc w, InIterator in, OutIterator out)
template<typename WeightFunc , typename Iterator >
bool	HasShortestPaths (int s, WeightFunc w, Iterator it)
template<typename WeightFunc >
void	FindPath_Directed (int t, WeightFunc w)
template<typename WeightFunc >
int	FindAPath_Directed (const set< int > &t, WeightFunc w)
template<typename WeightFunc >
void	FindAllPaths_Directed (WeightFunc w)
template<typename WeightFunc >
void	IncreaseUpdate_Directed (int u, int v, WeightFunc w)
template<typename WeightFunc >
void	DecreaseUpdate_Directed (int u, int v, WeightFunc w)
template<typename WeightFunc >
void	DeleteUpdate_Directed (int u, int v, WeightFunc w)
template<typename WeightFunc >
bool	HasShortestPaths_Directed (int s, WeightFunc w)
template<typename WeightFunc >
void	FindPath_Undirected (int t, WeightFunc w)
template<typename WeightFunc >
int	FindAPath_Undirected (const set< int > &t, WeightFunc w)
template<typename WeightFunc >
void	FindAllPaths_Undirected (WeightFunc w)
template<typename WeightFunc >
void	IncreaseUpdate_Undirected (int u, int v, WeightFunc w)
template<typename WeightFunc >
void	DecreaseUpdate_Undirected (int u, int v, WeightFunc w)
template<typename WeightFunc >
void	DeleteUpdate_Undirected (int u, int v, WeightFunc w)
template<typename WeightFunc >
bool	HasShortestPaths_Undirected (int s, WeightFunc w)
virtual void	SetDistance (int n, Real dn, int pn)

Public Attributes
const Graph< Node, Edge > &	g
std::vector< int >	p
std::vector< Weight >	d

Detailed Description

template<class Node, class Edge>
class Graph::ShortestPathProblem< Node, Edge >

Single-source shortest paths (Dijkstra's algorithm)

WeightFunc is a callback that returns the weight of an edge. More specifically, it returns a Weight when given an Edge,source,target as argument.

The start node(s) is set with InitializeSource(s)(). The resulting shortest path(s) are calculated using Find[A,All]Path(). The predecessor graph is stored in p (where -1 represents no predecessor) and d is the distance list.

FindPath returns when the target node t is reached. The variant FindAPath takes a set of target nodes, and produces the shortest path to one of those nodes. It returns the node. The variant FindAllPaths solves for all shortest paths.

This also allows dynamic updating of shortest paths. To increase an edge's weight, call IncreaseUpdate(), and to decrease an edge's weight, call DecreaseUpdate(). To remove an edge completely, call DeleteUpdate(). For a sequence of small graph changes these can save a lot of time over running the shortest path algorithm from scratch.

Member Function Documentation

template<class Node, class Edge>

virtual void Graph::ShortestPathProblem< Node, Edge >::SetDistance ( int  n, Real  dn, int  pn  )

inlinevirtual

Optional: a callback that is called to change the distance/parent to the node n. Subclasses can intercept this call if desired but it is the responsibility of the subclass to call 'd[n]=dn,p[n]=pn'. Otherwise undefined behavior will result!

Referenced by Graph::ShortestPathProblem< int, MultiModalPRM::TransitionInfo * >::SetDistance().

---

The documentation for this class was generated from the following file:

• ShortestPaths.h