アルゴリズム学習−Bellman−Ford(ベルマンフォード)アルゴリズム(C++実装)

BellmanFordアルゴリズム

長所短所

を実現
BellmanFordアルゴリズム
Bellman‐Fordアルゴリズムは単一ソース点最短経路アルゴリズムであり,このアルゴリズムの目的は図全体を見つけ,開始ノード(自分で定めた)最短経路と経路長に至ることである.
メリット/デメリット

の利点
このアルゴリズムの利点はDijkstraアルゴリズムに対して,負の重み経路があり,図中に負の重み回路があるかどうかを検出できることであるはずである.

の欠点
欠点は,負の重み回路を検出できるが,負の重み回路がある最短経路の問題は解決できないことである.また、時間の複雑さが高い.O(|V| * |E|).

インプリメンテーション
実際に実現される原理は、現在の図全体に対して1回の緩和操作を行うことである.全部で|V|回行います.各弛緩操作は|V|-1回の弛緩判定であった.
コード実装は次のとおりです.

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

#include <iostream>
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!
");
        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