GClasses
GClasses::GDijkstra Class Reference

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

#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
 

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