最短路径Shortest paths

寻找路径边权之和最小的路线。先区分单源与所有顶点对，再判断是否存在负权边或会影响目标的负环。

怎样选择#

具体算法	问题与前提	时间复杂度	辅助空间	选择与取舍
Dijkstra	单源；边权非负	索引二叉堆 $O((V+E)\log V)$	索引堆 $O(V)$ ；重复入堆版可 $O(V+E)$	确定最近的未处理顶点后不再回退；一般负权边会破坏这一保证。
Bellman–Ford	单源；允许负权边	$O(VE)$	$O(V)$ ，保存距离与前驱	反复松弛边，并检测从源点可达的负环；成本通常高于非负边权上的 Dijkstra。
Floyd–Warshall	所有顶点对；允许负权边	时间 $O(V^{3})$ ，空间 $O(V^{2})$	$O(V^{2})$ ，保存全对距离；路径恢复再用 $O(V^{2})$	适合顶点数适中的图；检查负对角项后，还需区分哪些顶点对受负环影响。

左右滑动查看完整对照。点击算法名称，查看原理、约束和实现。