讨论:贝尔曼-福特算法

贝尔曼-福特算法属于维基百科数学主题的基础条目第五级。请勇于更新页面以及改进条目。
本条目页属于下列维基专题范畴：

（获评未评级、低重要度）

	数学主题查论编本条目页属于数学专题范畴，该专题旨在改善中文维基百科数学类内容。如果您有意参与，请浏览专题主页、参与讨论，并完成相应的开放性任务。
未评	根据专题质量评级标准，本条目页尚未接受评级。
低	根据专题重要度评级标准，本条目已评为低重要度。

电脑和信息技术专题

（获评中重要度）

	信息技术主题查论编本条目页属于电脑和信息技术专题范畴，该专题旨在改善中文维基百科信息技术相关条目类内容。如果您有意参与，请浏览专题主页、参与讨论，并完成相应的开放性任务。
未评	根据专题质量评级标准，本条目页尚未接受评级。
中	根据专题重要度评级标准，本条目已评为中重要度。

此页面为第九次动员令的作品。
此条目属于自然与自然科学的作品之一，而此条目是一篇达标条目。

SPFA作者

最新留言：在8年前发布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 $NN^{3}$ 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的算法能在 $NN^{3}$ 个加法和比较运算之内求出最短路或检出负权环。在Bellman算法这类的标号修正法中，每个结点的距离都可能不断更新，直到算法结束时才能确定下来。）

关于SPFA

考虑到以下理由：

目前SPFA这个词在国内已经十分普及，尤其是算法竞赛当中，可说是人人皆知，甚至被传播到日本九州大学（[4]）。
个人认为这个名字并不具有很大的误导性。

如果贸然删除/合并SPFA相关的条目，会对读者造成很大不便。因此我认为应当修改所有关于SPFA的条目，指出：

“SPFA为标号修正法Bellman-Ford的别名。”
“带有标号修正的Bellman-Ford在1976年或更早就已存在。SPFA的别名由西南交通大学段凡丁于1994提出。”并在此处引用段凡丁论文
“SPFA算法在实际应用中效果良好。一般认为其期望复杂度为 $O(E)$ ；尚无已知的证明。最坏复杂度为 $O(V^{3})$ ，并且存在已知的方法可以构造特殊数据达到最坏情况。”并移除此处对段凡丁论文的引用。O(kE)的记号具有严重的误导性。请将时间复杂度写为O(E)，非渐进时间开销写为T(V,E) = kE，谢谢。

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

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

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

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

参见：en:Shortest Path Faster Algorithm

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

添加话题