单一路径
当需要立即获得所有中间跳时,使用本 API 生成路径。
单源 –> 单一目的(1–>1)
问题
获取单个源与单个目的之间的所有最低代价路径(或仅一条代表性的最低代价路径)。
在这种简单情形下,路由计算与路径集的检索可以在一次调用中完成,无需为后续调用缓存最短路径计算产生的信息。如果你需要在同一张网络上获取多条路径且边权重不断变化(例如在容量受限的路由中,选择一条路径会消耗容量并提高链路代价),请使用这种方式。
使用指南
选择其一:
-
prg_djk_path_get() — 运行 Dijkstra 算法并返回代价相等的路径集合。
-
prg_djk_path_get_options() — 如果只需要一条路径,用下面的方式可以更快地得到结果
prg_djk_path_get_with_options(..., ..., PRGC_DJK_PATH_GET_OPT_FIRST_FOUND)这样会跳过对(可能呈指数级庞大的)代价相等最短路径集合的考察。
边权重变化的图上的一系列路径
问题
获取一系列最短路径,其中较早的路径计算会改变后续路径计算所使用的边权重。
使用指南
对每条路径:
- prg_djk_edge_weight_set() — 设置用于最短路径(最小代价)计算的边权重。(每条边的默认权重为 1。)
- prg_djk_edge_disable(), prg_djk_vertex_disable() — 声明任何不可用的边和顶点。
- 遵循单源 –> 单一目的(1–>1)的使用指南。
- prg_djk_edge_enable(), prg_djk_vertex_enable() — 如有必要,恢复先前被禁用的边和顶点。
单源 –> 多目的或全部目的(1–>Many, 1–>All)
问题
获取单个源与多个(或全部)目的之间的路径集合。
最高效的做法是先计算状态信息,然后反复调用、一次检索一个路径集。
使用指南
-
prg_djk_single_source_compute() — 计算单个源到所有目的之间的最短路径,并将结果缓存在 predecessor_list 数据结构中。
注意: predecessor_list 存储(输出的)路径,其结构与(输入的)graph_cache 相互独立。
-
使用单对方式逐条检索源->目的路径(遵循单源 –> 单一目的(1–>1)的使用指南)。
对于多目的问题(相对于全部目的),使用 prg_djk_single_source_compute() 通常比反复调用 prg_djk_path_get() 更高效。一项针对示例网络的研究表明,在一个 100 节点的示例网络中,盈亏平衡点出现在需要求单个源到 12 个目的的路径时。
全部源 –> 全部目的(All–>All)
问题
求从所有源到所有目的的路径集合。
这种情况下,先为所有节点计算路由表、再逐对检索路径是高效的。
使用指南
- (可选)由于该计算可能耗时较长,可注册一个更新过程以定期产生进度报告。细节参见用户反馈。
- prg_djk_all_sources_compute() — 计算图中每个顶点的路由表,并将其作为状态信息存储在图中的每个顶点上。
- 对每一对(src, dest):
- prg_djk_path_get() — 检索每个源与目的之间的路径集合。该函数将利用存储在每个顶点路由表中的下一跳信息,构造每个源与目的之间的端到端路径。
- 不要调用任何
_disable()、_enable()、_weight_set()或_init()函数。
跳数限制的最短路径
跳数限制一般要求为图中的边设置非默认权重,否则除了某些簿记之外,问题仍然归结为最短路径问题。对于跳数限制,显式地对所有源进行循环,并使用单源 –> 单一目的(1–>1)或单源 –> 多目的或全部目的(1–>Many, 1–>All)的指导。