[ VIGRA Homepage | Function Index | Class Index | Namespaces | File List | Main Page ]

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

## ◆ run() [1/2]

template<class GRAPH , class WEIGHT_TYPE >
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

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.

## ◆ run() [2/2]

template<class GRAPH , class WEIGHT_TYPE >
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.

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.

## ◆ reRun()

template<class GRAPH , class WEIGHT_TYPE >
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

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.

## ◆ runMultiSource() [1/2]

template<class GRAPH , class WEIGHT_TYPE >
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.

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

## ◆ runMultiSource() [2/2]

template<class GRAPH , class WEIGHT_TYPE >
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.

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

© Ullrich Köthe (ullrich.koethe@iwr.uni-heidelberg.de) Heidelberg Collaboratory for Image Processing, University of Heidelberg, Germany | html generated using doxygen and Python vigra 1.12.1