基础最短路径算法：Dijkstra, Bellman-Ford, SPFA, Floyd-Warshall 的归纳

单源汇最短路径问题

这种问题给出一个起点，求该起点到其他点的最短路径。

边权为非负数

稠密图

建议使用邻接矩阵储存稠密图

朴素版 Dijkstra 算法：https://io.zouht.com/27.html

时间复杂度：$O({\left|V\right|}^2)$

其他算法

可处理负边权的算法可兼容非负权边情况、多源汇最短路算法可兼容单源汇情况。

稀疏图

建议使用邻接表储存稀疏图

二叉堆优化版 Dijkstra 算法：https://io.zouht.com/27.html

时间复杂度：$O((\left|E\right|+\left|V\right|)\log \left|V\right|)$

其他算法

可处理负边权的算法可兼容非负权边情况、多源汇最短路算法可兼容单源汇情况。

边权有负数

Bellman-Ford 算法：https://io.zouht.com/64.html

时间复杂度：$O(\left|V\right|\cdot \left|E\right|)$

SPFA：https://io.zouht.com/29.html

平均时间复杂度：$O(\left|E\right|)$

最差时间复杂度：$O(\left|V\right|\cdot \left|E\right|)$

多源汇最短路径问题

这种问题需要求任意起点到任意终点的最短路径。

Floyd-Warshall 算法：https://io.zouht.com/28.html

时间复杂度：$O({\left|V\right|}^3)$