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...
Public Member Functions |
| GDijkstra (size_t nodes) |
| ~GDijkstra () |
size_t | nodeCount () |
| Returns the number of nodes in the graph.
|
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.)
|
void | compute (size_t origin) |
| Finds the shortest-cost path from the specified origin to every other point in the graph.
|
double | cost (size_t target) |
| Returns the total cost to travel from the origin to the specified target node.
|
size_t | previous (size_t vertex) |
| Returns the previous node on the shortest path from the origin to the specified vertex.
|
Static Public Member Functions |
static void | test () |
| Performs unit tests for this class. Throws an exception if there is a failure.
|
Protected Attributes |
size_t | m_nodes |
double * | m_pCosts |
size_t * | m_pPrevious |
std::vector< size_t > * | m_pNeighbors |
std::vector< double > * | m_pEdgeCosts |
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))