最短路径问题 （一些乱七八糟的总结）

· BFS——单源无权最短路径

· Dijsktra——单源有权最短路径

· 无负权边

· 基于贪心

· 朴素版Dijsktra  O(n^2)  适用于稠密图       

//朴素版的基于链式前向星和邻接表的时间复杂度为 O((n+m)logn) ，对于稠密图来说比 O(n^2) 还慢。

· 堆优化版Dijsktra  O(mlogn)  适用于稀疏图

· Bellman-Ford——有向图单源有权最短路径

· 有负权边

· O(nm)

· SPFA——有向图单源有权最短路径

· Bellman-Ford的队列优化

· 可有负权边，不能有负环

· 一般O(m) 最坏O(nm)  

· Floyd——多源汇最短路

· 可有负权边

· 基于动态规划

· O(n^3)       //n<=800