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.

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.

本站文档由 北京智网畅联科技有限公司 整理、翻译并提供 · Documentation compiled and provided by Beijing ZNetLink Technology Co., Ltd.

交流群 · QQ Group:OPNET/智网妙算网络仿真交流群(群号 486383494)

原文档 © 2017 Riverbed Technology · 本站为公益翻译,由 AI 辅助完成,请仔细甄别

Original documentation © 2017 Riverbed Technology. Community translation, AI-assisted. Contact: jiazequn@znetlink.com