维基百科

Talk:贝尔曼-福特算法

最新留言：6年前由Billchenchina在话题3.2 队列优化是否应该变成一个单独条目？内发布
了解更多有关此页面的信息
基础条目 贝尔曼-福特算法属于维基百科數學主题的基礎條目第五級。请勇于更新页面以及改進條目。
          本条目页属于下列维基专题范畴：
数学专题 （获评未评級、低重要度）
本条目页属于数学专题范畴，该专题旨在改善中文维基百科数学类内容。如果您有意参与，请浏览专题主页、参与讨论，并完成相应的开放性任务。
 未评级未评  根据专题质量评级标准，本条目页尚未接受评级。
 低  根据专题重要度评级标准，本條目已评为低重要度。
电脑和信息技术专题 （获评中重要度）
本条目页属于电脑和信息技术专题范畴，该专题旨在改善中文维基百科資訊科技相关条目类内容。如果您有意参与，请浏览专题主页、参与讨论，并完成相应的开放性任务。
 未评级未评  根据专题质量评级标准，本条目页尚未接受评级。
 中  根据专题重要度评级标准，本條目已评为中重要度。


SPFA作者 编辑

最新留言：7年前1条留言1人参与讨论

在目前版本的条目中，提到“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.

在线阅读： [1] [2]

关于标号修正法及其在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，谢谢。

如果有更好的提议欢迎讨论。


附：有待更正的相关条目（不完全列表）

附：相关资料

sheep0x（留言） 2016年9月30日 (五) 09:22 (UTC)回复

3.2 队列优化是否应该变成一个单独条目？ 编辑

最新留言：6年前1条留言1人参与讨论

参见：en:Shortest Path Faster Algorithm

抱歉没有注意到上面的讨论，我认为应该添加与en:Shortest Path Faster Algorithm对应的SPFA算法，而不应该重定向—以上未簽名的留言由Ctyzxx（對話｜貢獻）於2017年8月12日 (六) 00:11 (UTC)加入。回复

添加话题
取自“https://zh.100ke.info/w/index.php?title=Talk:贝尔曼-福特算法&oldid=80882146”
返回到“贝尔曼-福特算法”页面。