ShortestPathDijkstra< GRAPH, WEIGHT_TYPE > Class Template Reference

shortest path computer More...

#include <vigra/graph_algorithms.hxx>

Public Member Functions
const DiscoveryOrder &	discoveryOrder () const
	get an array with all visited nodes, sorted by distance from source
WeightType	distance (const Node &target) const
	get the distance to a rarget node (after a call of run)
const DistanceMap &	distances () const
	get the distances node map (after a call of run)
const Graph &	graph () const
	get the graph
bool	hasTarget () const
	check if explicit target is given
const PredecessorsMap &	predecessors () const
	get the predecessors node map (after a call of run)
template<class WEIGHTS >
void	reRun (const WEIGHTS &weights, const Node &source, const Node &target=lemon::INVALID, WeightType maxDistance=NumericTraits< WeightType >::max())
	run shortest path again with given edge weights More...
template<class WEIGHTS >
void	run (const WEIGHTS &weights, const Node &source, const Node &target=lemon::INVALID, WeightType maxDistance=NumericTraits< WeightType >::max())
	run shortest path given edge weights More...
template<class WEIGHTS >
void	run (Node const &start, Node const &stop, const WEIGHTS &weights, const Node &source, const Node &target=lemon::INVALID, WeightType maxDistance=NumericTraits< WeightType >::max())
	run shortest path in a region of interest of a GridGraph. More...
template<class WEIGHTS , class ITER >
void	runMultiSource (const WEIGHTS &weights, ITER source_begin, ITER source_end, const Node &target=lemon::INVALID, WeightType maxDistance=NumericTraits< WeightType >::max())
	run shortest path with given edge weights from multiple sources. More...
template<class EFGE_WEIGHTS , class NODE_WEIGHTS , class ITER >
void	runMultiSource (const EFGE_WEIGHTS &edgeWeights, const NODE_WEIGHTS &nodeWeights, ITER source_begin, ITER source_end, const Node &target=lemon::INVALID, WeightType maxDistance=NumericTraits< WeightType >::max())
	run shortest path with given edge weights from multiple sources. More...
	ShortestPathDijkstra (const Graph &g)
	\ brief constructor from graph
const Node &	source () const
	get the source node
const Node &	target () const
	get the target node

Detailed Description

template<class GRAPH, class WEIGHT_TYPE>
class vigra::ShortestPathDijkstra< GRAPH, WEIGHT_TYPE >

shortest path computer

Member Function Documentation

void run	(	const WEIGHTS &	weights,
		const Node &	source,
		const Node &	target = lemon::INVALID,
		WeightType	maxDistance = NumericTraits<WeightType>::max()
	)

run shortest path given edge weights

Parameters

weights	: edge weights encoding the distance between adjacent nodes (must be non-negative)
source	: source node where shortest path should start
target	: target node where shortest path should stop. If target is not given or INVALID, the shortest path from source to all reachable nodes is computed
maxDistance	: path search is terminated when the path length exceeds maxDistance

When a valid target is unreachable from source (either because the graph is disconnected or maxDistance is exceeded), it is set to lemon::INVALID. In contrast, if target was lemon::INVALID at the beginning, it will always be set to the last node visited in the search.

void run	(	Node const &	start,
		Node const &	stop,
		const WEIGHTS &	weights,
		const Node &	source,
		const Node &	target = lemon::INVALID,
		WeightType	maxDistance = NumericTraits<WeightType>::max()
	)

run shortest path in a region of interest of a GridGraph.

Parameters

start	: first point in the desired ROI.
stop	: beyond the last point in the desired ROI (i.e. exclusive)
weights	: edge weights encoding the distance between adjacent nodes (must be non-negative)
source	: source node where shortest path should start
target	: target node where shortest path should stop. If target is not given or INVALID, the shortest path from source to all reachable nodes is computed
maxDistance	: path search is terminated when the path length exceeds maxDistance

This version of run() restricts the path search to the ROI [start, stop) and only works for instances of GridGraph. Otherwise, it is identical to the standard run() function.

void reRun	(	const WEIGHTS &	weights,
		const Node &	source,
		const Node &	target = lemon::INVALID,
		WeightType	maxDistance = NumericTraits<WeightType>::max()
	)

run shortest path again with given edge weights

This only differs from standard run() by initialization: Instead of resetting the entire graph, this only resets the nodes that have been visited in the previous run, i.e. the contents of the array discoveryOrder(). This will be much faster if only a small fraction of the nodes has to be reset.

void runMultiSource	(	const WEIGHTS &	weights,
		ITER	source_begin,
		ITER	source_end,
		const Node &	target = lemon::INVALID,
		WeightType	maxDistance = NumericTraits<WeightType>::max()
	)

run shortest path with given edge weights from multiple sources.

This is otherwise identical to standard run(), except that source() returns lemon::INVALID after path search finishes.

void runMultiSource	(	const EFGE_WEIGHTS &	edgeWeights,
		const NODE_WEIGHTS &	nodeWeights,
		ITER	source_begin,
		ITER	source_end,
		const Node &	target = lemon::INVALID,
		WeightType	maxDistance = NumericTraits<WeightType>::max()
	)

run shortest path with given edge weights from multiple sources.

This is otherwise identical to standard run(), except that source() returns lemon::INVALID after path search finishes.

---

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

• vigra/graph_algorithms.hxx