prg_djk_single_source_compute()
Abstract
Runs Dijkstra's shortest path algorithm and builds up a routing table at the source that includes next hops to all destinations in the graph.
Syntax
prg_djk_single_source_compute (src_vertex_ptr)
| Argument | Type | Description |
|---|---|---|
src_vertex_ptr |
PrgT_Graph_Vertex * |
The vertex at which to build the routing table. It is also used as the source vertex for the Dijkstra's shortest path algorithm. |
Return Type
PrgT_Compcode
PrgC_Compcode_Success if the routing table at the source has been built; PrgC_Compcode_Failure otherwise.
Header
prg_djk.h
Details
The function will run Dijkstra's shortest path algorithm on the graph with src_vertex_ptr as its source. After it determines the shortest paths to every destination, the function will build up a routing table at the source which, given a destination, will tell us what are the possible next hops we could take to get there.
If prg_djk_single_source_compute() is called multiple times, it will not recompute the routing table after it has been built the first time. If you want to re-run the shortest path computation, call prg_djk_graph_init() to re-initialize the routing tables at each node.
To get a routing table of the first hop from a single source to all destinations:
- Call
prg_djk_single_source_compute(). - Call prg_djk_next_hops_get() for each destination.
To get the set of paths between a single source and all destinations:
- Call prg_djk_graph_cache_enable() to make sure the route computation results will be saved.
- Call
prg_djk_single_source_compute(). - Make repeated calls to prg_djk_path_get() or prg_djk_path_get_options() to retrieve the paths one node-pair at a time.
- When you are finished with the path operations, or if a change to the graph has invalidated the current results, call prg_djk_graph_cache_disable() to free the cache.