prg_djk_single_source_compute()
摘要
运行 Dijkstra 最短路径算法,并在源处构建一张路由表,其中包含到图中所有目的地的下一跳。
语法
prg_djk_single_source_compute (src_vertex_ptr)
| 参数 | 类型 | 说明 |
|---|---|---|
src_vertex_ptr |
PrgT_Graph_Vertex * |
要在其上构建路由表的顶点,同时作为 Dijkstra 最短路径算法的源顶点。 |
返回类型
PrgT_Compcode
若源处的路由表已构建成功则返回 PrgC_Compcode_Success,否则返回 PrgC_Compcode_Failure。
头文件
prg_djk.h
详情
此函数将以 src_vertex_ptr 为源,在图上运行 Dijkstra 最短路径算法。在确定到每个目的地的最短路径之后,此函数会在源处构建一张路由表;给定一个目的地,该路由表可以告诉我们到达该目的地可选的下一跳有哪些。
如果多次调用 prg_djk_single_source_compute(),在第一次构建完成之后它不会重新计算路由表。如果想重新运行最短路径计算,调用 prg_djk_graph_init() 以重新初始化各节点上的路由表。
要获取从单一源到所有目的地的第一跳路由表:
- 调用
prg_djk_single_source_compute()。 - 对每个目的地调用 prg_djk_next_hops_get()。
要获取单一源与所有目的地之间的路径集合:
- 调用 prg_djk_graph_cache_enable(),确保路线计算结果会被保存。
- 调用
prg_djk_single_source_compute()。 - 反复调用 prg_djk_path_get() 或 prg_djk_path_get_options(),逐对节点地获取路径。
- 当路径操作完成,或者图的某项更改已使当前结果失效时,调用 prg_djk_graph_cache_disable() 释放缓存。