数据结构

DJK 包在 prg_graph 结构之上补充了计算最短路径并高效缓存相关信息所需的数据。这些数据一般只能通过 DJK API 访问,包括:

  • 图缓存(graph cache)——对图的一种描述形式:在其中修改图结构不方便,但在其上执行计算很高效。启用图缓存可以加快重复的最短路径计算。图缓存在添加或删除边或顶点之前都是有效的。当图结构发生变化时必须显式禁用缓存;DJK 包不会在内部跟踪缓存是否有效。 有关缓存维护的简单指导,参见实用函数与选项。
  • 前驱表(predecessor lists)——从某个源到所有目的的代价相等的最短路径集合的紧凑表示。 更多细节参见 predecessor list(前驱表)的定义。)
  • 路由表(routing tables)——从一个或多个源顶点到所有其他顶点(目的)的下一跳的紧凑描述。