最短路与MST模板以及不同算法间的对比思考

动态规划在某种意义上来说，动态规划的实质是有向无环图求单源点最MST短路

最短路问题求解异同总结

算法	适用条件	思想
BFS	所有边权相同，0/1 BFS可用于处理边权有0有1的情况(双向广搜)	把一步能到达的点加入队列通过一步能到达的点更新两步能到达的点，以此类推
拓扑排序+DP	适用于有向无环图	在拓扑排序过程中，现在入度为0的点最短路已经确定。而我们在枚举出边时再更新所有出边的最短路的值。
Dijkstra	适用于边权非负	因为思想里有个贪心，有负权边的话不符合贪心条件。
SPFA	本质上是个暴力	基于BFS，可能还与拓扑排序+DP有点像区别在于按拓扑序进行DP保证了无后效性，而SPFA可能有“后效性”

如果图中不存在长度为负数的边，那么类似于优先队列我们也可以使用二叉堆对算法进行优化，堆代替了一般的队列，用于保存带扩展的结点，每次取出“当前距离最小”的结点(堆顶)进行扩展，结点第一次从堆中被取出时，就得到了该点的最短路径。这与堆优化算法的流程完全一致。“二叉堆优化基于贪心的算法”和“优先队列优化基于的算法”两种思想殊途同归，都得到了非负权图上的单源最短路径算法。