跳转至

Bellman-Ford算法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <iostream>   

using namespace std;  

const int vertexNum = 5;      //定义有向图的顶点个数 
const int edgeNum = 10;       //定义有向图的边数 
const int INFINITE = 100000;  //定义无穷大的大小 

struct Edge { //边结构 
    int start;       //边的起点   
    int end;         //边的终点   
    int weight;      //边的权值 
};

struct Vertex { //顶点结构 
    int d;          //源点到该结点的最短路径估计 
    int p;          //该结点在最短路径树中的前驱结点
}; 

//程序只测试书中的一个测试用例，为方便起见，将顶点数组和边数组定义为全局变量 
Vertex V[vertexNum + 1];        //顶点数组 
Edge E[edgeNum + 1];            //边数组 

void insertEdge(int i, int start, int end, int weight) { //向边数组中插入边 
    E[i].start = start;
    E[i].end = end;
    E[i].weight = weight;
}

void initGraph() {  //为方便比对结果，插入边的顺序与书中P379上松弛操作对边的处理次序相同 
    insertEdge(1, 2, 3, 5);
    insertEdge(2, 2, 5, 8);
    insertEdge(3, 2, 4, -4);
    insertEdge(4, 3, 2, -2); 
    insertEdge(5, 5, 3, -3);
    insertEdge(6, 5, 4, 9);
    insertEdge(7, 4, 3, 7);
    insertEdge(8, 4, 1, 2);
    insertEdge(9, 1, 2, 6);
    insertEdge(10, 1, 5, 7);    
}

void initialize_Single_Source(int s) { //对最短路径估计和前驱结点进行初始化
    for (int i = 1; i <= vertexNum; i++) {
        V[i].d = INFINITE;
        V[i].p = -1;
    }
    V[s].d = 0;
}

void relax(int u, int v, int w) { //松弛操作 
    if (V[u].d != INFINITE && V[v].d > V[u].d + w) {
        V[v].d = V[u].d + w;
        V[v].p = u;
    }
}

void print() {  //输出顶点的属性 
    cout << "每个顶点的最短路径估计依次如下:" << endl; 
    for (int i = 1; i <= vertexNum; i++) {
        cout << V[i].d << " ";
    }
    cout << endl;
    cout << "每个顶点的前驱结点依次如下:" << endl; 
    for (int i = 1; i <= vertexNum; i++) {
        cout << V[i].p << " ";
    }
    cout << endl << endl;
}

bool bellman_Ford(int s) { //Bellman_Ford算法
    initialize_Single_Source(s);    //初始化
    for (int i = 1; i < vertexNum; i++) {    //对图的每条边进行vertexNUm-1次处理  
        cout << "== 第" << i << "轮：" << endl;
        for (int j = 1; j <= edgeNum; j++) { //依次对每条边进行松弛操作
            relax(E[j].start, E[j].end, E[j].weight);
        }
        print();  //输出每一轮松弛后的结果
    }
    for (int j = 1; j <= edgeNum; j++) {     //对负权回路进行检查
        if (V[E[j].end].d > V[E[j].start].d + E[j].weight) {
            return false;
        }       
    }
    return true;
}

int main() {
    initGraph();
    if (bellman_Ford(1)) {
        cout << "图中不存在可以从源结点到达的权重为负值的环路" << endl; 
    }
    else {
        cout << "图中存在可以从源结点到达的权重为负值的环路" << endl; 
    }
    return 0;
}