此页面的先前版本

双向 Dijkstra - 函数族

• pgr_bdDijkstra - 最短路径的双向 Dijkstra 算法。

• pgr_bdDijkstraCost - 双向 Dijkstra 计算最短路径的成本

• pgr_bdDijkstraCostMatrix - 创建最短路径成本矩阵的双向 Dijkstra 算法。

概要

基于 Dijkstra 算法，双向搜索找到起始顶点到结束顶点的最短路径。

它同时运行两项搜索：一项从源向前搜索，一项从目标向后搜索，当两者在中间相遇时停止。

该实现可以与有向图和无向图一起使用。

特征

主要特点是：

• 仅在具有正成本的边进行处理。

  • 成本列上的负值被解释为边不存在。

• 当存在路径时返回值。

• 当没有路径时：

  • 当起始顶点和结束顶点相同时。

    • 未包含值 \((v, v)\) 的 aggregate cost 为 \(0\)

  • 当起始顶点和结束顶点不同且不存在路径时：

    • 未包含值 \((u, v)\) 的 aggregate cost 是 \(\infty\)

• 出于优化目的，起始顶点或结束顶点中的任何重复值都将被忽略。

• 运行时间（最坏情况）： \(O((V \log V + E))\)

• 对于起始顶点和结束顶点之间存在路径的大型图:

  • 预计终止速度比 pgr_dijkstra 更快

另请参阅

索引和表格

• Index

• Search Page