跳转到内容

讨论:贝尔曼-福特算法

页面内容不支持其他语言。
维基百科,自由的百科全书
基础条目 贝尔曼-福特算法属于维基百科数学主题的基础条目第五级。请勇于更新页面以及改进条目。
          本条目页属于下列维基专题范畴:
数学专题 (获评未评级低重要度
本条目页属于数学专题范畴,该专题旨在改善中文维基百科数学类内容。如果您有意参与,请浏览专题主页、参与讨论,并完成相应的开放性任务。
 未评级未评  根据专题质量评级标准,本条目页尚未接受评级。
   根据专题重要度评级标准,本条目已评为低重要度
电脑和信息技术专题 (获评中重要度
本条目页属于电脑和信息技术专题范畴,该专题旨在改善中文维基百科信息技术相关条目类内容。如果您有意参与,请浏览专题主页、参与讨论,并完成相应的开放性任务。
 未评级未评  根据专题质量评级标准,本条目页尚未接受评级。
   根据专题重要度评级标准,本条目已评为中重要度


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.

在线阅读: [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 队列优化是否应该变成一个单独条目?

[编辑]

参见:en:Shortest Path Faster Algorithm

抱歉没有注意到上面的讨论,我认为应该添加与en:Shortest Path Faster Algorithm对应的SPFA算法,而不应该重定向—以上未签名的留言由Ctyzxx对话贡献)于2017年8月12日 (六) 00:11 (UTC)加入。[回复]