无向加权图中多次查询两点最短路径的高效算法探究

通用场景（任意两点查询） #

针对多次查询任意两点最短路径的需求，有以下更高效的方案：

• Floyd-Warshall算法：一次性计算所有节点对的最短路径，时间复杂度为O(V³)，后续查询仅需O(1)时间。该算法实现简单，适合节点数V较小的场景（比如V≤1000），但当V过大时（如上万级），时间开销会急剧上升。
• 双向Dijkstra算法：每次查询时同时从起点和终点出发，运行Dijkstra算法，当两个搜索路径相遇时停止。对于稀疏图（你的图E≈3V属于此类），该算法的单次查询效率通常远高于单向Dijkstra，尤其适合两点距离较近的场景，且无需预先计算所有节点对的距离。
• Johnson算法：适用于存在负权边（无负权环）的稀疏图，先通过Bellman-Ford算法计算势能重新赋权，再对每个节点运行堆优化的Dijkstra。时间复杂度为O(V E logV)，和多次单向Dijkstra相当，但能处理负权边场景。

约束场景（仅查询n个预定义节点间的距离） #

如果仅需查询指定的n个节点之间的任意距离，算法选择会更高效：

• 多源Dijkstra：仅对这n个预定义节点分别运行堆优化的Dijkstra算法，记录每个预定义节点到所有其他节点的距离。时间复杂度为O(n E logV)，若n远小于总节点数V，相比对所有节点跑Dijkstra，时间开销会大幅降低。后续查询直接从预存的距离表中取值即可。
• A*算法（若适用）：如果图具备可利用的启发信息（比如地理图中的直线距离），可以用A*算法加速预定义节点间的查询。通过启发函数引导搜索方向，能显著减少需要遍历的节点数，但要求启发函数满足可采纳性（即不会高估剩余距离）。

结合你的稀疏图特点的建议 #

你的图边数约为节点数的3倍，属于典型稀疏图：

• 若总节点数较少，优先选Floyd-Warshall，实现简单且查询快捷；
• 若总节点数较大且需任意两点查询，用双向Dijkstra处理单次查询更高效；
• 若仅需查询预定义节点间的距离，直接对这些节点跑多源Dijkstra是最优选择，兼顾时间和空间效率。

内容的提问来源于stack exchange，提问作者Lithanium