bellman-ford算法

发表于

简介

贝尔曼-福特算法（英语：Bellman–Ford algorithm），求解单源最短路径问题的一种算法，由理查德·贝尔曼（Richard Bellman） 和 莱斯特·福特 创立的。有时候这种算法也被称为 Moore-Bellman-Ford 算法，因为 Edward F. Moore 也为这个算法的发展做出了贡献。它的原理是对图进行次松弛操作，得到所有可能的最短路径。其优于迪科斯彻算法的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高。但算法可以进行若干种优化，提高了效率。其中一种优化是改变数据结构，改成队列，还有对无效点进行跳过等等。

题目

就是一个有向图，指定起点，查找到其他点的最短路径。
输入第一行是 顶点数 边数量
第二行是 起点 终点 权值
默认源点是1点

输入

5 5
2 3 2
1 2 -3
1 5 5
4 5 2
3 4 3

输出

0 -3 -1 2 4

代码

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
#include<iostream>

using namespace std;

int vert_length = 5;
int line_length = 5;
int inf = 999999;
int vert1[5] = {1, 0, 0, 3, 2}, vert2[5] = { 2, 1, 4, 4, 3 }, w[5] = { 2, -3, 5, 2, 3 };
int dis[5], book[5];
int start;

void init() {
	for (int i = 0; i < vert_length; i++)
	{
		if (i == start)
		{
			dis[i] = 0;
		}
		else
		{
			dis[i] = inf;
		}
	}
}

void findPath() {
	
	bool isLoop = false;

	init();

	for (int i = 0; i < vert_length - 1; i++)
	{
			for (int j = 0; j < vert_length; j++)
			{
				book[j] = dis[j];
			}

			for (int j = 0; j < line_length; j++)
			{
				if (dis[vert2[j]] > dis[vert1[j]] + w[j])
				{
					dis[vert2[j]] = dis[vert1[j]] + w[j];
				}
			}

			bool isFinal = true;

			for (int k = 0; k < vert_length; k++)
			{
				if (book[k] != dis[k]) {
					isFinal = false;
					break;
				}
			}

			if (isFinal)
			{
				break;
			}

	}

	for (int j = 0; j < line_length; j++)
	{
		if (dis[vert2[j]] > dis[vert1[j]] + w[j])
		{
			isLoop = true;
		}
	}

	if (isLoop) {
		cout << "存在负权回环" << endl;
	}
}

void main() {
	start = 0;
	findPath();
	for (int i = 0; i < vert_length; i++)
	{
		cout << dis[i] << " ";
	}
}

思路

这个算法其实和dijkstra算法很像，核心就是插入一个点，看加起来的权值是否比原来不加的少。还有一个思想就是两个点的最短路径，一定是一个简单路径，不存在回环这种情况。
还有就是最外面的循环，第一次找到了通过两条边的最短路径，第二次找到通过三条边的最短路径，我们可以从中得到一种结论，这个就要自己好好思考了。