算法學習 - Bellman-Ford（貝爾曼福特）算法(C++實現)

BellmanFord算法 優點缺點 實現

BellmanFord算法

Bellman-Ford算法是一個單源點最短路徑算法，這個算法的目的就是找到整個圖，到起始節點（自己定的）最短的路徑和路徑長度。

優點/缺點

優點

這個算法的優點應該是相對Dijkstra算法來說的，就是可以有負權值路徑並且能檢測到圖中是否有負權值回路。

缺點

缺點就是雖然能檢測負權值回路，但是解決不了有負權值回路的最短路徑問題。 還有就是時間復雜度比較高。 O(|V| * |E|).

實現

其實實現的原理就是：每次對當前整個圖進行一次松弛操作。一共進行|V|次。 每次的松弛操作都是|V|-1次的松弛判斷。

下面是代碼實現：

//
//  main.cpp
//  BellmanFord
//
//  Created by Alps on 15/3/26.
//  Copyright (c) 2015年 chen. All rights reserved.
//

#include 
using namespace std;

#ifndef NumVertex
#define NumVertex 4
#endif

#ifndef Infinity
#define Infinity 1000
#endif

typedef int Vertex;

struct LinkList{
    int val;
    int weight;
    LinkList * next;
    LinkList(int v, int w): val(v), weight(w), next(NULL){}
};

typedef LinkList* VList;

struct TableEntry{
    VList Header;
    Vertex Dist;
    Vertex Path;
};

typedef TableEntry Table[NumVertex+1];

void InitTable(Vertex start, Table T){

    int OutDegree = 0;
    VList temp = NULL;

    for (int i = 1; i <=NumVertex; i++) {
        T[i].Header = NULL; // init the vertex
        T[i].Dist = Infinity;
        T[i].Path = -1;

        scanf("%d",&OutDegree);

        for (int j = 0; j < OutDegree; j++) { // init the link vertex
            temp = (VList)malloc(sizeof(struct LinkList));
            scanf("%d %d", &temp->val, &temp->weight);
            temp->next = T[i].Header;
            T[i].Header = temp;
        }

    }

    T[start].Dist = 0;
}

void PrintPath(Vertex V, Table T){
    if (T[V].Path != -1) {
        PrintPath(T[V].Path, T);
        printf(" to ");
    }
    printf("%d", V);
}

bool BellFord(Vertex start, Table T){
    bool Update = false;
    VList temp;

    for (int i = 1; i <= NumVertex; i++) { //cycle the num of vertex
        Update = false;

        for (int j = 1; j <= NumVertex; j++) { // traversal all the vertex
            if (T[j].Dist != Infinity) { // if the current vertex distance is not Inf
                temp = T[j].Header;
                while (temp != NULL) { // if it have traversaled the link vertex
                    if (T[j].Dist + temp->weight < T[temp->val].Dist) { //if need to relax
                        T[temp->val].Dist = T[j].Dist + temp->weight; //relax operation
                        T[temp->val].Path = j; // mark the path
                        Update = true; // mark the vertex update is true
                    }
                    temp = temp->next; // find the next node
                }
            }
        }
    }

    if (Update == true) {
        return false; // if the Graph have a negative cycle
    }else{
        return true; // no negative cycle
    }
}

int main(int argc, const char * argv[]) {
    Table T;

    InitTable(1, T);

    if (!BellFord(1, T)) {
        printf("There is a cycle!\n");
        return 0;
    }

    PrintPath(3, T);

    return 0;
}

測試用例：
case: 
    2 //第一個節點的出度
    2 -1//節點id和到節點2的length
    3 1
    2 //第二個節點的出度
    3 -2 //同理
    4 1
    1
    4 -1
    0

上面的圖就是：
節點1 -> 2(-1)->3(1)
節點2->3(-2)->4(1)
節點3->4(-1)
節點4