Talk:贝尔曼-福特算法
![]() |
贝尔曼-福特算法属于维基百科數學主题的基礎條目第五級。请勇于更新页面以及改進條目。 本条目页属于下列维基专题范畴: |
||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
![]() | 此頁面為第九次動員令的作品。 此條目屬於自然與自然科學的作品之一,而此條目是一篇達標條目。 |
SPFA作者
[编辑]在目前版本的条目中,提到“SPFA算法是西南交通大学段凡丁于1994年发表的”。但早在1975(1976)年就已存在相同的算法,名为“带修正的Bellman-Ford”。
关于“SPFA即是标号修正法的Bellman-Ford”的证据
[编辑]在Bertsekas的1993年论文当中,提到
“In label correcting methods, the selection of the node to be removed from V is faster than in label setting methods, at the expense of multiple entrances of nodes in V. These methods use a queue Q to maintain the candidate list V. Nodes can be inserted or removed from the queue in O(1) operations;” ...(略)... “At each iteration the node removed from V is the top node of Q.” 翻译:比起固定标号法,标号修正法在V中选择结点的速度更快。标号修正法使用一个队列Q来维护候选列表V。结点可以在O(1)个操作之内加入/弹出队列。……每轮选取Q的队首,从V中移除。(这里比较绕。V指的是候选点集,比如Dijkstra的堆和SPFA的队列。Q和V是同一个东西,V是抽象数据结构,Q是具体实现。)
并且指出有三种“流行的”入队方法。其中一种便是“The Bellman-Ford method”:“the node that enters V, is added at the bottom of Q. Thus, nodes enter and exit V in first-in/first-out fashion.”(翻译:进入V的结点被加进Q的队尾。换言之,V是一个先进先出的数据结构。)
该论文甚至提及当今流行的两大“SPFA优化”之一:SLF(另一优化为LLL)。进一步证明了SPFA实际就是Bellman-Ford变种的别名。
论文: D.P. Bertsekas. A simple and fast label correcting algorithm for shortest paths. Networks, 23:703–709, 1993.
关于标号修正法及其在Bellman-Ford上的应用的发明时间
[编辑]暂未找到原作者和原论文(原始论文可能并不存在)。目前我考察到的最早的文献是1976年Bruce L. Golden的论文:
Golden, B., 1976. “Shortest-Path Algorithms: A Comparison,” Operations Research, Vol.44, pp. 1164-1168.
可以在这里阅读:[3]
关于标号修正法:“Labeling methods for computing shortest paths can be divided into two general classes, "label-setting" and "label-correcting" methods”(译文:求最短路的算法可以粗分为两大类:固定标号法和标号修正法。)
关于标号修正法的Bellman-Ford:“Bellman's algorithm solves the problem in at most additions and comparisons or detects the existence of a negative cycle. This algorithm is an example of the label-correcting approach in which no node labels are considered permanent until they all are, at termination.”(译文:Bellman的算法能在个加法和比较运算之内求出最短路或检出负权环。在Bellman算法这类的标号修正法中,每个结点的距离都可能不断更新,直到算法结束时才能确定下来。)
关于SPFA
[编辑]考虑到以下理由:
- 目前SPFA这个词在国内已经十分普及,尤其是算法竞赛当中,可说是人人皆知,甚至被传播到日本九州大学([4])。
- 个人认为这个名字并不具有很大的误导性。
如果贸然删除/合并SPFA相关的条目,会对读者造成很大不便。因此我认为应当修改所有关于SPFA的条目,指出:
- “SPFA为标号修正法Bellman-Ford的别名。”
- “带有标号修正的Bellman-Ford在1976年或更早就已存在。SPFA的别名由西南交通大学段凡丁于1994提出。”并在此处引用段凡丁论文
- “SPFA算法在实际应用中效果良好。一般认为其期望复杂度为;尚无已知的证明。最坏复杂度为,并且存在已知的方法可以构造特殊数据达到最坏情况。”并移除此处对段凡丁论文的引用。O(kE)的记号具有严重的误导性。请将时间复杂度写为O(E),非渐进时间开销写为T(V,E) = kE,谢谢。
如果有更好的提议欢迎讨论。
附:有待更正的相关条目(不完全列表)
- 贝尔曼-福特算法
- en:Shortest_Path_Faster_Algorithm
- sr:Brži_algoritam_najkraćeg_puta
- http://www.nocow.cn/index.php/SPFA
附:相关资料
sheep0x(留言) 2016年9月30日 (五) 09:22 (UTC)
3.2 队列优化是否应该变成一个单独条目?
[编辑]参见:en:Shortest Path Faster Algorithm
抱歉没有注意到上面的讨论,我认为应该添加与en:Shortest Path Faster Algorithm对应的SPFA算法,而不应该重定向—以上未簽名的留言由Ctyzxx(對話|貢獻)於2017年8月12日 (六) 00:11 (UTC)加入。