Question

关于Dijkstra、SPFA、Bellman-Ford、Floyed算法的问题

总觉得这几个算法的基本框架都差不多，都看重 v[i]>=v[j]+g[i,j] 这个不等式，SPFA是队列优化的Bellman-Ford，但我觉得SPFA如果不用邻接表用起来好像也就跟Dijkstra差不多......
痛苦啊，迷茫啊......神牛快来丫......总觉得这几个差不多......如果是NOIP提高组，需要掌握的有什么？

Answer 1

bellman-ford可以有负权，但不能态枯有负权回路，

spfa是bellman-ford的队列优化，时间发咋度o（ke），其中k为所有顶点进队的平均次数，可以证明k一般小于等于念漏2。

dijkstra不可以有负权，但效率比bellman-ford快，o（2n次方），用二叉堆优化o((m+n)log n)，斐波纳契堆能稍微提高一些性能，让算法运行时间达到o(m + n log n)。

floyed算每对顶点之间的最短路，前几个是单源的

noip提高组多练搜索，学会动态规划差不多了，其他的模拟提都简单，主要是多练题帆高洞

纯手打

Answer 2

最近我对Dijkstra、SPFA、Bellman-Ford进行了大规模测试顷搭(10000个点)
当边数<10000*100 SPFA具有平均优势
当边数超过上述数, SPFA将逊于Dijkstra
关于Bellman-Ford算法的快速实施,除了SPFA,国际上最有竞争力的是划分算法(Partitioning algorithm), 加入门槛技巧,是最快的最短路算法. 远比SPFA有竞争力,而且划分算法是强多项式算法.
我的测试表明, 划分算法不加入门槛帆乎念技术,仅仅稍微略逊于SPFA. 门槛技术不过操作起来不态困太方便. 不要再迷信SPFA了, 它的迭代次数一般为2,经我的测试是不靠谱的,和划分算法的迭代次数相差不大(按照SPFA的迭代次数衡量), 是大家对Bellman-Ford算法的实施了解得不够.
我的邮件为hwy000111@163.com.有关最短路的可以与我交流.