prg_djk_k_paths_max_visitations_set()
Abstract
Sets the maximum number of visitations allowed at a node when computing the k shortest paths on a graph.
Syntax
prg_djk_k_paths_max_visitations_set (graph_ptr, visitation_limit)
| Argument | Type | Description |
|---|---|---|
graph_ptr |
PrgT_Graph * |
The graph of interest. |
visitation_limit |
int |
The number of visitations to permit, or PRGC_DJK_UNLIMITED_VISITATIONS for an unlimited number. |
Return Type
PrgT_Compcode
PrgC_Compcode_Success if the operation succeeds; PrgC_Compcode_Failure otherwise.
Header
prg_djk.h
Details
During a k paths compute algorithm run, the visitation limit is set by default to the k value. This function overrides that default.
In the Dijkstra algorithm, a node is “visited” when a new route is found to the node and the node is added to the list of nodes to expand. In the simplest version of the shortest path algorithm, only the first visit is important because the first visit will be the shortest path. However, with various options (edge consider procedures, path consider procedures, path acceptance procedures, hop limits, and k-paths), it is necessary to allow more than a single visitation. In the simple k-paths case, the visitation limit is set to k. However, when an acceptance procedure is specified, the default is set to unlimited. The visitation limit can be used by the client to limit the computation time to avoid a potentially exponential run time.
Note: When a visitation limit is used, the algorithm can fail to find the optimal k-shortest paths. When the algorithm detects that it cannot guarantee that the k-paths are the optimal set, it will terminate with the set of paths that it has computed thus far. This set of paths is the set of shortest paths; however, it may include fewer than k-paths.