最短路

目的

寻找图中从一个点到另一个点的路径

一个点到其他点的最短路

最短路径算法	描述
Dijkstra	该算法要求所有路径的权值为非负数
Bellman-Ford(SPFA)	该算法允许路径的权值为负数

任意两点间的最短路

最短路径算法	描述
Floyd-Warshall	允许非环路的路径权值为负数该算法不仅适用于稀疏图，在稠密图（路径数量多的图）中寻找最短路径的效率也很高。
Johnson	允许非环路的路径权值为负数该算法更适用于稀疏图（路径数量少的图）