prg_djk_k_paths_max_visitations_set()
摘要
设置在图上计算 k 条最短路径时每个节点允许的最大访问次数。
语法
prg_djk_k_paths_max_visitations_set (graph_ptr, visitation_limit)
| 参数 | 类型 | 说明 |
|---|---|---|
graph_ptr |
PrgT_Graph * |
目标图。 |
visitation_limit |
int |
允许的访问次数;若不限次数,则取 PRGC_DJK_UNLIMITED_VISITATIONS。 |
返回类型
PrgT_Compcode
操作成功时返回 PrgC_Compcode_Success,否则返回 PrgC_Compcode_Failure。
头文件
prg_djk.h
详情
在 k 路径计算算法的运行过程中,访问次数限制的默认值为 k 值。此函数可以覆盖该默认值。
在 Dijkstra 算法中,当找到到达某节点的新路由、并且该节点被加入待扩展节点列表时,该节点即被“访问”。在最简单的最短路径算法版本中,只有第一次访问是重要的,因为第一次访问对应的就是最短路径。然而,在使用各种选项(边 consider 过程、路径 consider 过程、路径接受过程、跳数限制以及 k 路径)时,就需要允许不止一次访问。在简单的 k 路径情形下,访问次数限制被设置为 k;但当指定了接受过程时,默认值被设置为不限。客户端可以利用访问次数限制来控制计算时间,以避免可能呈指数级的运行时间。
**注意:**使用访问次数限制时,算法可能无法找到最优的 k 条最短路径。当算法检测到它无法保证所得的 k 条路径是最优集合时,将以至此已计算出的路径集合作为结果终止。该路径集合是最短路径集合,但其中包含的路径数可能少于 k 条。