一.最短路线
最短路径：从图中的一个顶点出发到达另一个顶点的通过边的权重和最小路径。
求出最短路径的四种算法如下。
二.算法概述
【Dijkstra算法】
单源最短路径：从单一源点出发，到所有节点的最短路径
作用：计算正权图上的单源短路最多。
图类型：有向图、有向图。
限制：边权为正。
【Bellman-Ford算法】
事实1 :负的权利存在的情况下，连最短路的也不一定存在。
事实2 :存在短路最多的情况下，必然存在不含环的短路最多。
作用：计算图上的单源短路最多(前提是存在短路最多)。
图类型：有向图、有向图。
优势：边境权可以负。
【Floyd算法】
作用：求两点之间的最短路。
图类型：有向图、有向图。
特征：为了在Dijkstra或Bellman-ford中求出各两点之间的最短短路，需要调用n次Dijkstra (边权全部为正)或Bellman-ford (带负)。
三.负权问题
如果某个图只有负的权利，而不构成负的权利回路呢？
Dijkstra算法
如上图所示，如果以a为源点，则在第一个循环后，b以标记数组进行标记，但在第二个循环中，b还可以在c点继续更新。 由此可以得出结论，Dijkstra算法不适用于负权重图。
Bellman_Ford算法和SPFA算法
上述“因为b点是用标记数组标记的，所以不能用c点更新”的问题，让我们考虑一下最终还是标记数组的锅。 有人建议可以删除标记数组，但如果删除，则会成为严重的问题。 首先，可能会出现“无法求出dist[]的最小值”。
相反，Bellman_Ford和SPFA算法不存在标记数组问题，因此对于只存在负权重的图也能很好地发挥作用。
最后，在无向图的情况下，如果有1条负的边，需要注意该图中存在负的权重回路。 很容易理解这是无向图的1条边相当于有向图的往返2条边。
四.补充分析
Dijkstra、Bellman_Ford和SPFA，用哪个好呢？
Bellman_Ford什么也没说。 不用的话请不要用。
国际上普遍不承认SPFA算法。 因为SPFA算法论文中对其复杂性的证明存在错误。 然后Bellman_Ford的论文提到了这个队列的优化。
SFA算法有两种优化策略SLF和LLL。
小型标签首次战略。 将参加节点设为j，团队领导要素设为I，如果是dist[j] dist[i]，则将j插入团队领导，否则插入团队领导；
ll，Large Label Last战略中，将队列的开头要素设为I，将队列内所有dist值的平均值设为x，dist[i] x将I插入队列的末尾，直到发现某个I为止，dist[i]=x，则I从队列中出来
SLF可使速度提高15 ~ 20%，SLF LLL可提高约50%。 在实际的APP应用中，SPFA算法的时间效率不是很稳定，并且一般使用的是更稳定高效的Dijkstra算法，以便避免发生最坏情况。
利用邻表二叉树优化的戴克斯特拉方法复杂度合适且稳定，但存在缺点，无法处理负权重电路。
最后听了话，我发现在算法竞赛中我们的很多选择还是SPFA。 众所周知，邻表两股优化的Dijkstra编写起来很复杂，容易出错，但SPFA代码简单，容易写，但会被主题卡数据。
总结： Dijkstra优先，其次是SPFA，最后是Bellman_Ford优先。 具体采用哪种方法，要看情况而定。