算法随笔：各种经典最短路算法的简要比较总结

有多种最短路径的应用场景，它们需要用到不同的算法来解决。除了贪心最优搜索之外，其他都是最优性算法，即得到的解都是最短路径。其中m是边的数量，n是点的数量。

问题	边权	算法	时间复杂度
一个起点，一个终点	非负数；无边权（或边权为1）	A*算法	<O((m+n)logn)
		双向搜索	<O((m+n)logn)
		贪心最优搜索	<O(m+n)
一个起点到其他所有点	无边权（或边权为1）	BFS	O(m+n)
	非负数	Dijkstra（堆优化）	O((m+n)logn)
	允许有负数	SPFA	<O(mn)
所有点对之间	允许有负数	Floyd	O(n^3)

应该在不同的场景下有选择地使用。

（1）图的规模小，并且要求多源最短路，那么使用Floyd，如果边权有负数，则需要判断负环。

（2）图的规模大，且边的权值非负，用Dijkstra，SPFA虽然在Bellman-Ford算法上进行了很大的优化，但是最坏情况下依然是O(mn)，不稳定（比赛时，有的题目可能故意利用SPFA的不稳定性，如果一道题目的图规模很大，并且边的权值为非负数，它可能会故意设置不利于SPFA的测试数据，此时使用SPFA将会超时，要使用更稳定的Dijkstra）。

（3）图的规模很大，且边的权值有负数，用SPFA，并且需要判断负环。