使用场景
DJK 包的所有使用场景都需要一些共同的准备工作。总体流程是:
- 初始化一个图。
- 启用缓存。
- 设置边权重。
- 执行所需的计算。
- 检索计算出的路径或跳。
各使用场景的特定步骤在后续小节中讨论。在本文档中,我们假设你已经构建了一个 PrgT_Graph。有关构建图的说明,参见第 6 章 “Graph Package”(第 121 页)。
以下步骤是所有使用场景共有的:
-
prg_djk_graph_init() — 初始化一个供 DJK 算法使用的图。
-
prg_djk_graph_cache_enable() — 开启对内部用于表示图的高效数据结构的缓存,使每次 prg_djk_path_get() 调用不必重新索引图。当图发生变化(创建或删除顶点或边)时,必须先禁用缓存,然后再重新启用。
注意: 该图缓存不包含(输出的)路径数据,只包含(输入的)图数据。
-
prg_djk_edge_weight_set() — 设置用于最短路径(最小代价)计算的边权重。(每条边的默认权重为 1。)
-
(可选) 有关更多选项和回调函数,参见实用函数与选项。
-
(可选) 定义边和节点的可接受性过滤器;定义并注册
consider_proc回调,用于强制实施无法用边权重表达的约束。a) prg_djk_consider_proc_register() — (动态局部约束) 注册一个用于判定某条边是否可用于最短路径的函数。通常更高效的做法是提前“修剪”图,即移除或禁用(参见 prg_djk_edge_disable())那些不应出现在最短路径中的边。在其他情况下,使用
consider_proc回调更好,例如当**:**– 某条边的可接受性取决于从源到该边的部分路径代价。
– 某条边的可接受性会在多次最短路径计算的过程中发生变化。一个常见的情形是共享某种资源(如链路带宽)的路由需求。当本包返回一条路由后,客户端代码记录资源消耗;在计算下一条路由时,
consider_proc以即时方式禁用已被完全占用的链路。b) prg_djk_path_consider_proc_register() — (动态全局约束) 注册一个用于判定某条部分路径是否可接受的函数。当某条边的可接受性取决于路径中的其他跳(而不仅仅是路径代价)时,使用该回调。
-
prg_djk_graph_init() 也可在这些调用之后使用,以释放所有缓存的路由状态信息。