Dijkstra算法:

1.本算法求解指定两点间的最短路,或从指定点到其余各点的最短路。

2.本算法目前被认为是求无负权网络最短路问题的最好方法。

3.本算法基于贪心算法。

4.基本流程:

1. 初始化所有顶点到源点的距离。

2. while 循环找到最近的顶点 u 进行标记。

3. 在 while 循环中,更新顶点 u 的所有出边顶点 v 到源点的距离。方程可得: 

4. 循环直到所有顶点标记完就 break。

5. 最终 dis[i] 中存的都是源点到 i 点的最短路径值。

Floyd算法:

算法特点:Floyd 算法是解决任意两点的最短路径的一种算法,可以正确处理有向图,可带有负权(但不可存在负权回路)的最短路径问题.

算法思路: 对于每一对顶点 u 和 v,看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比 u->v 的路径最短,如果是,更新他.

算法结果: edge[i][j] 为 i 到 j 的最短路径.

算法优点: 代码简单,适合求多源最短路径.

算法缺点:时间复杂度较高O(),不适合大量数据.

注：有些地方叫 Flody，是同一种算法。

SPFA算法:

本算法用来求解单源最短路径的算法,和 dijkstra 算法不同在于,SPFA能够存在负权值,但不能有负环.但是，关于SPFA,他死了——时间复杂度太高！具体可以去知乎参考：zhihu.com/question/292283275