討論:貝爾曼-福特算法

貝爾曼-福特算法屬於維基百科數學主題的基礎條目第五級。請勇於更新頁面以及改進條目。
本條目頁屬於下列維基專題範疇：

（獲評未評級、低重要度）

	數學主題閱論編本條目頁屬於數學專題範疇，該專題旨在改善中文維基百科數學類內容。如果您有意參與，請瀏覽專題主頁、參與討論，並完成相應的開放性任務。
未評	根據專題品質評級標準，本條目頁尚未接受評級。
低	根據專題重要度評級標準，本條目已評為低重要度。

電腦和信息技術專題

（獲評中重要度）

	資訊科技主題閱論編本條目頁屬於電腦和信息技術專題範疇，該專題旨在改善中文維基百科資訊科技相關條目類內容。如果您有意參與，請瀏覽專題主頁、參與討論，並完成相應的開放性任務。
未評	根據專題品質評級標準，本條目頁尚未接受評級。
中	根據專題重要度評級標準，本條目已評為中重要度。

此頁面為第九次動員令的作品。
此條目屬於自然與自然科學的作品之一，而此條目是一篇達標條目。

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)加入。回覆

新增話題