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

Typedefs
typedef std::vector< WEMNode * >	WEMNodeVector
	Internal vector holds the temporary WEMNode front nodes.

Functions
MLWEM_EXPORT void	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 *	_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 *	_extractMax (double &distances, WEMPatch wemPatch)
	Helper method: searches for the node with maximal distance, and returns a pointer to this node.

void	_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 namespace 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.

Typedef Documentation

◆ WEMNodeVector

typedef std::vector<WEMNode*> ml::WEMShortestPath::WEMNodeVector

Internal vector holds the temporary WEMNode front nodes.

Definition at line 33 of file WEMShortestPath.h.

Function Documentation

◆ _addToBorder()

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.

References _addToBorder().

Referenced by _addToBorder().

◆ _extractMax()

WEMNode * ml::WEMShortestPath::_extractMax	(	double *&	distances,
		WEMPatch *	wemPatch )

Helper method: searches for the node with maximal distance, and returns a pointer to this node.

References _extractMax().

Referenced by _extractMax().

◆ _extractMin()

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.

References _extractMin().

Referenced by _extractMin().

◆ shortestPath()

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.

The path is stored in pathNodesEntryNumbers, as the entry numbers of visited nodes including the start node and destination node. If for destNode a NULL pointer is provided, the path to the most distant geodetic point is calculated.

References shortestPath().

Referenced by shortestPath().

Typedefs

Functions