使用场景

DJK 包的所有使用场景都需要一些共同的准备工作。总体流程是:

  1. 初始化一个图。
  2. 启用缓存。
  3. 设置边权重。
  4. 执行所需的计算。
  5. 检索计算出的路径或跳。

各使用场景的特定步骤在后续小节中讨论。在本文档中,我们假设你已经构建了一个 PrgT_Graph。有关构建图的说明,参见第 6 章 “Graph Package”(第 121 页)。

以下步骤是所有使用场景共有的:

  1. prg_djk_graph_init() — 初始化一个供 DJK 算法使用的图。

  2. prg_djk_graph_cache_enable() — 开启对内部用于表示图的高效数据结构的缓存,使每次 prg_djk_path_get() 调用不必重新索引图。当图发生变化(创建或删除顶点或边)时,必须先禁用缓存,然后再重新启用。

    注意: 该图缓存不包含(输出的)路径数据,只包含(输入的)图数据。

  3. prg_djk_edge_weight_set() — 设置用于最短路径(最小代价)计算的边权重。(每条边的默认权重为 1。)

  4. (可选) 有关更多选项和回调函数,参见实用函数与选项。

  5. (可选) 定义边和节点的可接受性过滤器;定义并注册 consider_proc 回调,用于强制实施无法用边权重表达的约束。

    a) prg_djk_consider_proc_register() — (动态局部约束) 注册一个用于判定某条边是否可用于最短路径的函数。通常更高效的做法是提前“修剪”图,即移除或禁用(参见 prg_djk_edge_disable())那些不应出现在最短路径中的边。在其他情况下,使用 consider_proc 回调更好,例如当**:**

    – 某条边的可接受性取决于从源到该边的部分路径代价。

    – 某条边的可接受性会在多次最短路径计算的过程中发生变化。一个常见的情形是共享某种资源(如链路带宽)的路由需求。当本包返回一条路由后,客户端代码记录资源消耗;在计算下一条路由时,consider_proc 以即时方式禁用已被完全占用的链路。

    b) prg_djk_path_consider_proc_register() — (动态全局约束) 注册一个用于判定某条部分路径是否可接受的函数。当某条边的可接受性取决于路径中的其他跳(而不仅仅是路径代价)时,使用该回调。

  6. 各使用场景的特定步骤,见以下小节:单一路径、路由表 和 多路径与拓扑规划。

  7. prg_djk_graph_init() 也可在这些调用之后使用,以释放所有缓存的路由状态信息。