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

算法学习 - Bellman-Ford（贝尔曼福特）算法(C++实现)

BellmanFord算法

优点/缺点

实现