GClasses
|
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 |
GClasses::GDijkstra::GDijkstra | ( | size_t | nodes | ) |
GClasses::GDijkstra::~GDijkstra | ( | ) |
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.
|
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 |
Performs unit tests for this class. Throws an exception if there is a failure.
|
protected |
|
protected |
|
protected |
|
protected |
|
protected |