单一路径

当需要立即获得所有中间跳时,使用本 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)
    

    这样会跳过对(可能呈指数级庞大的)代价相等最短路径集合的考察。

边权重变化的图上的一系列路径

问题

获取一系列最短路径,其中较早的路径计算会改变后续路径计算所使用的边权重。

使用指南

对每条路径:

  1. prg_djk_edge_weight_set() — 设置用于最短路径(最小代价)计算的边权重。(每条边的默认权重为 1。)
  2. prg_djk_edge_disable(), prg_djk_vertex_disable() — 声明任何不可用的边和顶点。
  3. 遵循单源 –> 单一目的(1–>1)的使用指南。
  4. prg_djk_edge_enable(), prg_djk_vertex_enable() — 如有必要,恢复先前被禁用的边和顶点。

单源 –> 多目的或全部目的(1–>Many, 1–>All)

问题

获取单个源与多个(或全部)目的之间的路径集合。

最高效的做法是先计算状态信息,然后反复调用、一次检索一个路径集。

使用指南

  1. prg_djk_single_source_compute() — 计算单个源到所有目的之间的最短路径,并将结果缓存在 predecessor_list 数据结构中。

    注意: predecessor_list 存储(输出的)路径,其结构与(输入的)graph_cache 相互独立。

  2. 使用单对方式逐条检索源->目的路径(遵循单源 –> 单一目的(1–>1)的使用指南)。

    对于多目的问题(相对于全部目的),使用 prg_djk_single_source_compute() 通常比反复调用 prg_djk_path_get() 更高效。一项针对示例网络的研究表明,在一个 100 节点的示例网络中,盈亏平衡点出现在需要求单个源到 12 个目的的路径时。

全部源 –> 全部目的(All–>All)

问题

求从所有源到所有目的的路径集合。

这种情况下,先为所有节点计算路由表、再逐对检索路径是高效的。

使用指南

  1. (可选)由于该计算可能耗时较长,可注册一个更新过程以定期产生进度报告。细节参见用户反馈。
  2. prg_djk_all_sources_compute() — 计算图中每个顶点的路由表,并将其作为状态信息存储在图中的每个顶点上。
  3. 对每一对(src, dest):
    • prg_djk_path_get() — 检索每个源与目的之间的路径集合。该函数将利用存储在每个顶点路由表中的下一跳信息,构造每个源与目的之间的端到端路径。
    • 不要调用任何 _disable()、_enable()、_weight_set() 或 _init() 函数。

跳数限制的最短路径

跳数限制一般要求为图中的边设置非默认权重,否则除了某些簿记之外,问题仍然归结为最短路径问题。对于跳数限制,显式地对所有源进行循环,并使用单源 –> 单一目的(1–>1)或单源 –> 多目的或全部目的(1–>Many, 1–>All)的指导。

本站文档由 北京智网畅联科技有限公司 整理、翻译并提供 · 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