GClasses::GDijkstra Class Reference

Finds the shortest path from an origin vertex to all other vertices. Implemented with a binary-heap priority-queue. If the graph is sparse on edges, it will run in about O(n log(n)) time. If the graph is dense, it runs in about O(n^2 log(n)) More...

#include <GGraph.h>

Public Member Functions
	GDijkstra (size_t nodes)
	~GDijkstra ()
void	addDirectedEdge (size_t from, size_t to, double cost)
	Adds a directed edge to the graph. (You must call this to add all the edges before calling compute.) More...
void	compute (size_t origin)
	Finds the shortest-cost path from the specified origin to every other point in the graph. More...
double	cost (size_t target)
	Returns the total cost to travel from the origin to the specified target node. More...
size_t	nodeCount ()
	Returns the number of nodes in the graph. More...
size_t	previous (size_t vertex)
	Returns the previous node on the shortest path from the origin to the specified vertex. More...

Static Public Member Functions
static void	test ()
	Performs unit tests for this class. Throws an exception if there is a failure. More...

Protected Attributes
size_t	m_nodes
double *	m_pCosts
std::vector< double > *	m_pEdgeCosts
std::vector< size_t > *	m_pNeighbors
size_t *	m_pPrevious

Detailed Description

Finds the shortest path from an origin vertex to all other vertices. Implemented with a binary-heap priority-queue. If the graph is sparse on edges, it will run in about O(n log(n)) time. If the graph is dense, it runs in about O(n^2 log(n))

Constructor & Destructor Documentation

GClasses::GDijkstra::GDijkstra

(

size_t

nodes

)

GClasses::GDijkstra::~GDijkstra

(

)

Member Function Documentation

void GClasses::GDijkstra::addDirectedEdge	(	size_t	from,
		size_t	to,
		double	cost
	)

Adds a directed edge to the graph. (You must call this to add all the edges before calling compute.)

void GClasses::GDijkstra::compute

(

size_t

origin

)

Finds the shortest-cost path from the specified origin to every other point in the graph.

double GClasses::GDijkstra::cost

(

size_t

target

)

Returns the total cost to travel from the origin to the specified target node.

size_t GClasses::GDijkstra::nodeCount ( )

inline

Returns the number of nodes in the graph.

size_t GClasses::GDijkstra::previous

(

size_t

vertex

)

Returns the previous node on the shortest path from the origin to the specified vertex.

static void GClasses::GDijkstra::test ( )

static

Performs unit tests for this class. Throws an exception if there is a failure.

Member Data Documentation

size_t GClasses::GDijkstra::m_nodes

protected

double* GClasses::GDijkstra::m_pCosts

protected

std::vector<double>* GClasses::GDijkstra::m_pEdgeCosts

protected

std::vector<size_t>* GClasses::GDijkstra::m_pNeighbors

protected

size_t* GClasses::GDijkstra::m_pPrevious

protected