Determine the least cost path between nodes in a graph. More...

#include <WsfShortestPath.hpp>

Public Types
typedef std::vector< std::vector< int > >	CostMatrix

Public Member Functions
	WsfShortestPath ()
bool	Initialize (const CostMatrix &aCostMatrix)
void	FindShortestPath (unsigned int aFromNode, unsigned int aToNode, int &aCost, std::vector< int > &aPath)

Detailed Description

Determine the least cost path between nodes in a graph.

This class uses the Dijkstra algorithm to determine the least cost path in a graph. The graph is defined by a cost matrix with the following attributes:

A matrix element [m][n] with a value greater that zero implies that node 'm' is ADJACENT to node 'n'. This defines an 'edge' in the graph with endpoints 'm' and 'n'. The value of the element is the cost of going from node 'm' to node 'n'.
A matrix element [m][n] with a value less than zero implies that node 'm' is NOT ADJACENT to node 'n'.
The matrix must be square.
The matrix must be symmetric, i.e., element [m][n] must equal to [n][m]. (This means the that the cost of the path from 'a' to 'b' will be equal to the cost from 'b' to 'a').

Member Typedef Documentation

◆ CostMatrix

typedef std::vector<std::vector<int> > WsfShortestPath::CostMatrix

Constructor & Destructor Documentation

◆ WsfShortestPath()

WsfShortestPath::WsfShortestPath ( )

Member Function Documentation

◆ FindShortestPath()

void WsfShortestPath::FindShortestPath	(	unsigned int	aFromNode,
		unsigned int	aToNode,
		int &	aCost,
		std::vector< int > &	aPath )

Find the shortest path between two nodes.

Parameters

aFromNode	[input] The starting node.
aToNode	[input] The ending node.
aCost	[output] The cost of the path. This will be < 0 if a path could not be generated.
aPath	[output] A vector of nodes that define the path. This will be empty if a path could not be generated.

Note: Initialize() must be called before invoking this method.

◆ Initialize()

bool WsfShortestPath::Initialize ( const CostMatrix & aCostMatrix )

Initialize the shortest path algorithm.

The cost matrix defines the cost of going between two ADJACENT nodes (the algorithm also uses this to determine which nodes are adjacent). The matrix must have the following properties:

It must be square (have the same number of rows and columns)
Entry [m][n] defines the cost of going from node 'm' to node 'n', where nodes 'm' and 'n' are adjacent. If nodes 'm' and 'n' are not adjacent then this value must be <= 0.
It must be symmetric (A[m][n] == A[n][m]. The cost of going from 'm' to 'n' must be the same as the cost of going from 'n' to 'm'.

Parameters

aCostMatrix The cost matrix.

Returns: 'true' if successful or 'false' if not.

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

Public Types

Public Member Functions