MeVisLab/Standard/Sources/ML/MLWEM/WEMTools/WEMGraphAlgorithms/WEMShortestPath.h File Reference

The WEMShortestPath class implements Dijkstra's shortest path algorithm for a WEM. More...

#include "WEMTools/WEMToolsIncludes.h"
#include <algorithm>

Go to the source code of this file.

Namespaces
namespace	ml
	Define the namespace name like in the ML. Default is ml.
namespace	ml::WEMShortestPath
	The WEMShortestPath namespace implements Dijkstra's shortest path algorithm for a WEM.
Defines
#define	WEM_SHORTESTPATH_TRAVERSED_BIT   15
	Shortest path traversed bit.
Typedefs
typedef std::vector< WEMNode * >	ml::WEMShortestPath::WEMNodeVector
	Internal vector holds the temporary WEMNode front nodes.
Functions
MLWEM_EXPORT void	ml::WEMShortestPath::shortestPath (WEMPatch *wemPatch, WEMNode *startNode, WEMNode *destNode, std::vector< unsigned int > &pathNodesEntryNumbers)
	Computes the shortest path along edges of the wemPatch, from the startNode to the destNode.
WEMNode *	ml::WEMShortestPath::_extractMin (WEMNodeVector &R, double *&distances)
	Helper method: searches for the shortest edge in the WEMNodeVector R, erases the according node from R and returns a pointer to this node.
WEMNode *	ml::WEMShortestPath::_extractMax (double *&distances, WEMPatch *wemPatch)
	Helper method: searches for the node with maximal distance, and returns a pointer to this node.
void	ml::WEMShortestPath::_addToBorder (WEMNodeVector &R, WEMNode *node, double *distances, WEMNode **previousNodes)
	Helper method: adds all unvisited nodes to R, and updates the distances array and the previousNodes array.

---

Detailed Description

The WEMShortestPath class implements Dijkstra's shortest path algorithm for a WEM.

If a start and a destination node is given, the shortest path is returned as a vector of the entry numbers of the nodes on the shortest path (including the start and destination node). Running time is O(n2) in the worst case, but the algorithm terminates if the destination node is reached. If for destNode a NULL pointer is provided, the path to the most distant geodetic point is calculated.

Author:

Olaf Konrad, Bart De Dobbelaer

Date:

8/2007

Definition in file WEMShortestPath.h.

---

Define Documentation

#define WEM_SHORTESTPATH_TRAVERSED_BIT   15

Shortest path traversed bit.

Definition at line 29 of file WEMShortestPath.h.