Single-Source Shortest Path:Bellman-Ford Algorithm

Posted by Chiu CC on 3 01, 2016


先備知識與注意事項

本篇文章將介紹Bellman-Ford Algorithm來回應上一篇Single-Source Shortest Path:Intro(簡介)的問題,演算法的概念主要圍繞在:

  • Relaxation
  • Convergence property
  • Path-relaxation property

建議讀者可以先進傳送門精彩回顧一下。


目錄


Graph之表示法(representation)

BFS/DFS系列文章使用Adjacency List代表Graph,不過edge上沒有weight,可以使用如下資料結構:

  • std::vector<std::list<int>> AdjList;

MST系列文章的Graph利用Adjacency Matrix,因此可以使用如下資料結構,把weight放進矩陣之元素:

  • std::vector<std::vector<int>> AdjMatrix;

本篇文章將利用Adjacency List來代表weighted edge,方法是使用C++標準函式庫(STL)的std::pair<int,int>,使得AdjList的資料結構更新為:

  • std::vector<std::list<std::pair<int,int>>> AdjList;

若有一條從vertex(0)(from)指向vertex(1)(to)的edge(0,1)之weight為\(5\),若利用新的AdjList表示,如圖一:

  • fromstd::vectorindex表示;
  • 每一個std::pair<int,int>都是一個std::list的node;
  • to放在std::pair<int,int>的第一個int資料項;
  • weight放在std::pair<int,int>的第二個int資料項,

關於std::pair<int,int>的用法,可以參考:Cplusplus:std::pair

cc

圖一。


Bellman-Ford Algorithm

根據Path-Relaxation Property,考慮一條從vertex(0)到vertex(K)之路徑\(P:v_0-v_1-...-v_K\),如果在對path之edge進行Relax()的順序中,曾經出現edge(v0,v1)、edge(v1,v2)、...、edge(vK-1,vK)的順序,那麼這條path一定是最短路徑,滿足distance[K]\(=\delta(v_0,v_K)\)

  • 在對edge(v1,v2)進行Relax()之前,只要已經對edge(v0,v1)進行過Relax(),那麼,不管還有其餘哪一條edge已經進行過Relax()distance[2]必定會等於\(\delta(0,2)\),因為Convergence property

Bellman-Ford Algorihm就用最直覺的方式滿足Path-Relaxation Property

  • 一共執行\(|V|-1\)次迴圈。
  • 在每一次迴圈裡,對「所有的edge」進行Relax()
  • 經過\(|V|-1\)次的「所有edge之Relax()」後,必定能夠產生「按照最短路徑上之edge順序的Relax()順序」,也就能夠得到最短路徑。
    • 由於從起點走到任一vertex之最短路徑,最多只會有\(|V|-1\)條edge,因此,執行\(|V|-1\)次迴圈必定能夠滿足「最壞情況」(worst case)。


考慮如圖二(a)之Graph,以vertex(0)作為起點。
並且根據圖二(a)之Adjacency List,得到在Bellman-Ford Algorihm中對所有edge進行Relax()之順序如圖二(b)。

cc

圖二(a)。

cc

圖二(b):根據圖二(a)之AdjList,對所有edge進行Relax()之順序。


首先,對Graph的資料項目distancepredecessor進行初始化,見圖二(c):

  • distance:將起點vertex之distance設為\(0\),並將其餘vertex之distance設為無限大(\(\infty\))。
    • 如果在演算法結束後,某個vertex之distance仍然無限大(\(\infty\)),則表示Graph中沒有一條path能夠從起點vertex走到該vertex。
    • 回顧Relax(),因為只有起點vertex(0)之distance設為\(0\),其餘distance都是無限大,因此,在進行「所有edge之Relax()」時,一定是從與起點vertex(0)相連之edge先開始。
  • predecessor:將所有vertex之predecessor設為\(-1\),表示目前還沒有predecessor。對其餘vertex來說,可以想成還沒有被起點vertex找到。

cc

圖二(c)。


接著開始\(|V|-1\)次的迴圈,並在每次迴圈,都對「所有edge」進行Relax()
(此例,共\(5\)次迴圈,每次按照圖二(b)之順序處理\(10\)條edge)。

第一次迴圈(iteration#1)

對第一條edge(0,1)進行Relax(),見圖三(a):

  • 比較distance[1]distance[0]+w(0,1),發現」從vertex(0)走到vertex(1)」之成本較原先的成本低(原先的成本即為distance[1]),因此更新distance[1]distance[0]+w(0,1)
  • 同時更新predecessor[1]=0,表示vertex(1)是從vertex(0)走過去的。

cc

圖三(a)。

對第二、三條edge(1,2)、edge(1,4)進行Relax(),見圖三(b):

  • 由於distance[2]distance[4]皆大於從vertex(1)走過去的成本,因此更新:
    • distance[2]=distance[1]+w(1,2)
    • distance[4]=distance[1]+w(1,4)

cc

圖三(b)。

對第四、五條edge(2,4)、edge(2,5)進行Relax(),見圖三(c):

  • 由於distance[4]小於「從vertex(2)走過去的成本(distance[2]+w(2,4)),因此,仍維持從vertex(1)走到vertex(4)之路徑。
  • distance[5]大於distance[2]+w(2,5),因此更新:
    • distance[5]=distance[2]+w(2,5)
    • predecessor[5]=2

cc

圖三(c)。

對第六條edge(3,2)進行Relax(),見圖三(d):

  • 顯然,「從vertex(1)走到vertex(2)」之成本distance[2]遠小於「從vertex(3)走到vertex(2)」之成本distance[3]+w(2,3),因此,不更新抵達vertex(2)之路徑。

cc

圖三(d)。

對第七、八條edge(4,3)、edge(4,5)進行Relax(),見圖三(e):

  • 由於distance[3]大於從vertex(4)走到vertex(3)的成本(distance[4]+w(4,3)),因此更新:
    • distance[3]=distance[4]+w(4,3)
    • predecessor[3]=4
  • 而且distance[5]也大於distance[4]+w(4,5),表示「從vertex(4)走到vertex(5)」會比「從vertex(2)走到vertex(5)」還近,便更新:
    • distance[5]=distance[4]+w(4,5)
    • predecessor[5]=4

cc

圖三(e)。

對第九、十條edge(5,0)、edge(5,1)進行Relax(),見圖三(f):

  • 比較distance及edge之weight後發現,從vertex(5)走到vertex(0)與vertex(1)之成本皆高於當前走到此二vertex之路徑,因此不更新。

cc

圖三(f)。

經過了第一次迴圈的洗禮,大致能夠掌握Relax()的精髓:如果有比目前的成本更低的路徑,就選擇那條路徑。
例如,圖三(c)中,原本從vertex(0)走到vertex(5)的路徑是\(Path:0-1-2-5\),但是在圖三(e)時,發現了更短的路徑\(Path:0-1-4-5\),便更新其成為目前「從vertex(0)走到vertex(5)」的最短路徑。

還有沒有可能更新出成本更低的路徑?

當然有,因為第一次迴圈的Relax()明顯沒有更新到和edge(3,2)有關路徑,其原因在於,Relax()進行的edge順序
在第一次迴圈中,是先對edge(3,2)進行Relax(),不過此時的distance[3]還是無限大,因此沒有作用,之後才更新出「從vertex(4)走到vertex(3)」的路徑。
就圖三(f)看來,distance[2]\(11\),而\(Path:0-1-4-3-2\)之成本只有\(6\),顯然是低於當前的路徑\(Path:0-1-2\)

因此需要\(|V|-1\)次迴圈,以確保演算法一定能找到最短路徑。


第二次直到第五次迴圈的邏輯同上,在此就不再贅述。

最後得到的最短路徑之Predecessor Subgraph如圖三(g):

cc

圖三(g)。

根據圖三(g),從vertex(0)走到Graph中其餘vertex之最短路徑為\(Path:0-1-4-3-2-5\),若把Bellman-Ford Algorithm中,每一次迴圈對所有edge進行Relax()之順序攤開,如圖三(h),可以驗證Bellman-Ford Algorithm確實滿足Path-Relaxation Property,按照最短路徑之順序對edge進行Relax()
(Bellman-Ford Algorithm就是暴力解決,當然會滿足。)

cc

圖三(h)。


程式碼

程式碼包含幾個部分:

class Graph_SP

  • 使用AdjList,並利用std::pair<int,int>儲存edge的weight。
  • InitializeSingleSource(int Start):對資料項目distancepredecessor進行初始化,並以int Start作為最短路徑之起點。
  • Relax():對edge進行Relaxation的主要函式。
  • BellmanFord():進行Bellman-Ford Algorithm的主要函式,內容如前一小節所述。

以及main():建立如圖二(a)之AdjList,並進行BellmenFord()

// C++ code
#include <iostream>
#include <vector>
#include <list>
#include <utility>          // for std::pair<>
#include <iomanip>          // for std::setw()

const int Max_Distance = 100;
class Graph_SP{             // SP serves as Shortest Path
private:
    int num_vertex;
    std::vector<std::list<std::pair<int,int>>> AdjList;
    std::vector<int> predecessor, distance;
public:
    Graph_SP():num_vertex(0){};
    Graph_SP(int n):num_vertex(n){
        AdjList.resize(num_vertex);
    }
    void AddEdge(int from, int to, int weight);
    void PrintDataArray(std::vector<int> array);

    void InitializeSingleSource(int Start);     // 以Start作為起點
    void Relax(int X, int Y, int weight);       // 對edge(X,Y)進行Relax
    bool BellmanFord(int Start = 0);            // 以Start作為起點
                                                // if there is negative cycle, return false
};

bool Graph_SP::BellmanFord(int Start){

    InitializeSingleSource(Start);

    for (int i = 0; i < num_vertex-1; i++) {                // |V-1|次的iteration
        // for each edge belonging to E(G)
        for (int j = 0 ; j < num_vertex; j++) {             // 把AdjList最外層的vector走一遍
            for (std::list<std::pair<int,int> >::iterator itr = AdjList[j].begin();
                 itr != AdjList[j].end(); itr++) {          // 各個vector中, 所有edge走一遍
                Relax(j, (*itr).first, (*itr).second);
            }
        }
    }

    // check if there is negative cycle
    for (int i = 0; i < num_vertex; i++) {
        for (std::list<std::pair<int,int> >::iterator itr = AdjList[i].begin();
             itr != AdjList[i].end(); itr++) {
            if (distance[(*itr).first] > distance[i]+(*itr).second) {   // i是from, *itr是to
                return false;
            }
        }
    }

    // print predecessor[] & distance[]
    std::cout << "predecessor[]:\n";
    PrintDataArray(predecessor);
    std::cout << "distance[]:\n";
    PrintDataArray(distance);

    return true;
}
void Graph_SP::PrintDataArray(std::vector<int> array){
    for (int i = 0; i < num_vertex; i++)
        std::cout << std::setw(4) << i;
    std::cout << std::endl;
    for (int i = 0; i < num_vertex; i++)
        std::cout << std::setw(4) << array[i];
    std::cout << std::endl << std::endl;
}
void Graph_SP::InitializeSingleSource(int Start){

    distance.resize(num_vertex);
    predecessor.resize(num_vertex);

    for (int i = 0; i < num_vertex; i++) {
        distance[i] = Max_Distance;
        predecessor[i] = -1;
    }
    distance[Start] = 0;
}
void Graph_SP::Relax(int from, int to, int weight){

    if (distance[to] > distance[from] + weight) {
        distance[to] = distance[from] + weight;
        predecessor[to] = from;
    }
}
void Graph_SP::AddEdge(int from, int to, int weight){
    AdjList[from].push_back(std::make_pair(to,weight));
}

int main(){

    Graph_SP g7(6);
    g7.AddEdge(0, 1, 5);
    g7.AddEdge(1, 4, -4);g7.AddEdge(1, 2, 6);
    g7.AddEdge(2, 4, -3);g7.AddEdge(2, 5, -2);
    g7.AddEdge(3, 2, 4);
    g7.AddEdge(4, 3, 1);g7.AddEdge(4, 5, 6);
    g7.AddEdge(5, 0, 3);g7.AddEdge(5, 1, 7);

    if (g7.BellmanFord(0))
        std::cout << "There is no negative cycle.\n";
    else
        std::cout << "There is negative cycle.\n";

    return 0;
}

output:

predecessor[]:
   0   1   2   3   4   5
  -1   0   3   4   1   2

distance[]:
   0   1   2   3   4   5
   0   5   6   2   1   4

There is no negative cycle.


檢查Graph中是否存在negative cycle

聰明的讀者一定已經發現了,BellmanFord()還有個功能,可以檢查Graph中是否存在negative cycle
上一篇文章Single-Source Shortest Path:Intro(簡介)曾經提到,塵世間最痛苦的事情莫過於在處理Single-Source Shortest Path問題時碰上negative cycle,因為negative cycle存在會使得最短路徑出現\(-\infty\)

若存在從vertex(from)指向vertex(to)的edge(from,to),並具有weight,根據Relax()的運作原則,:

  • distance[to]\(>\)distance[from]+weight,便更新distance[to]=distance[from]+weight」。

因此,在對Graph中所有edge進行Relax()後,所有edge(from,to)所連結的兩個vertex之distance必定滿足:

  • distance[to]\(\leq\)distance[from]+weight

BellmanFord()的檢查方法,便是在\(|V|-1\)次「對所有edge進行Relax()」後,檢查,若存在任何一條edge(from,to)所連結的兩個vertex之distance關係為:

  • distance[to]\(>\)distance[from]+weight

就表示存在某一條edge之weight永遠可以讓該edge連結之vertex的distance下降,因此Graph中必定存在negative cycle。


以上便是Bellman-Ford Algorithm之介紹。
只要了解:

  • Relaxation
  • Convergence property
  • Path-relaxation property

之概念,即可掌握Bellman-Ford Algorithm的運作邏輯。

下一篇文章將介紹的是,在DAG(directed acyclic graph)中處理Single-Source Shortest Path之演算法。



參考資料:


Shortest Path系列文章

Shortest Path:Intro(簡介)
Single-Source Shortest Path:Bellman-Ford Algorithm
Single-Source Shortest Path:on DAG(directed acyclic graph)
Single-Source Shortest Path:Dijkstra's Algorithm
All-Pairs Shortest Path:Floyd-Warshall Algorithm

回到目錄:

目錄:演算法與資料結構