图的最短路径-Bellman-Ford算法

Dijkstra算法无法解决带有负权边的图，为此要用到Bellman-Ford算法（贝尔曼-福特算法）

算法思路如下：

  1. 在第一次遍历前，先假定从起点到各点的距离都为正无穷
  2. 枚举每一条边，若发现该边可以使起点到某一点的路径变短，则更新距离
  3. 由于在n个顶点的图中，最短路径最多有n-1条边，所以将第2步循环n-1次。

总结：

因为最短路径最多有n-1条边，因此Bellman-Ford算法最多有n-1个阶段。每个阶段中，我们对每一条边进行松弛操作，在进行完n-1个阶段后，我们得出最多经过n-1条边的最短路径。

该算法可以判定带有负权环的图，

可见有的顶点的最短路径在中途就已经确定，但每次还需要判断，因此这里有优化空间（添加布尔值判断和基于队列优化）

示例代码：

整体代码：

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
//最短路径——贝尔曼-福特算法
#include<iostream>
using namespace std;
#define inf 999999;

int city, road;
//城市数量和道路数量

//贝尔曼-福特算法
void bellmanFord(int* u,int* v,int* w,int start)
{
	//初始化dis数组,这里记录起点到其余各点的初始距离，在开始遍历之前先默认距离为无穷大
	int* dis = new int[city + 1];
	for (int i = 1; i <= city; i++) dis[i] = inf;
	dis[start] = 0;

	//bellmanFord算法开始遍历
	for (int i = 0; i < city - 1; i++)//遍历的次数为顶点数减一
	{
		bool check = false;//判断是否有松弛
		for (int j = 0; j < road; j++)//遍历每一条边，从u，到v，路程（权）w
		{
			if (dis[v[j]] > dis[u[j]] + w[j])//如果起点到v的距离大于 从起点到u再从u到v的距离
			{
				dis[v[j]] = dis[u[j]] + w[j];//利用uv进行“松弛”
				check = true;
			}
		}
		if (check == false)//没有发生松弛，则说明已经结束
		{
			break;
		}
	}

	//输出结果
	for (int i = 1; i <= city; i++)
	{
		cout << dis[i] << " ";
	}

	delete[] dis;
}

int main()
{
	cin >> city >> road;
	//城市和道路
	int* u = new int[road];//边的起点数组
	int* v = new int[road];//边的终点数组
	int* w = new int[road];//边的权数组
	for (int i = 0; i < road; i++)
	{
		cin >> u[i] >> v[i] >> w[i];
	}

	bellmanFord(u, v, w, 1);
	
	return 0;
}

核心代码：

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
//贝尔曼-福特算法
void bellmanFord(int* u,int* v,int* w,int start)
{
	//初始化dis数组,这里记录起点到其余各点的初始距离，在开始遍历之前先默认距离为无穷大
	int* dis = new int[city + 1];
	for (int i = 1; i <= city; i++) dis[i] = inf;
	dis[start] = 0;

	//bellmanFord算法开始遍历
	for (int i = 0; i < city - 1; i++)//遍历的次数为顶点数减一，即n-1次
	{
		bool check = false;//判断是否有松弛
		for (int j = 0; j < road; j++)//遍历每一条边，从u，到v，路程（权）w
		{
			if (dis[v[j]] > dis[u[j]] + w[j])//如果起点到v的距离大于 从起点到u再从u到v的距离
			{
				dis[v[j]] = dis[u[j]] + w[j];//利用uv进行“松弛”
				check = true;
			}
		}
		if (check == false)//没有发生松弛，则说明已经结束
		{
			break;
		}
	}

	//输出结果
	for (int i = 1; i <= city; i++)
	{
		cout << dis[i] << " ";
	}

	delete[] dis;
}
  • 在每个阶段对每一条边进行松弛操作
  • 进行n-1轮松弛后，若仍有边满足松弛条件，则图中有负权环

基于队列优化代码

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
bool* book = new bool[city + 1];
for (int i = 1; i <= city; i++) book[i] = false;//初始化标记数组

int queue[2502];
int head = 0;
int tail = 0;//初始化队列

queue[tail++] = start;
book[start] = true;//起点入队

while (head != tail)//当队列不为空时
{
	for (int i = 0; i < road; i++)//遍历每一条边，这里用邻接表还能更快
	{
		if (u[i] == queue[head])//对出边进行判断
		{
			if (dis[v[i]] > dis[u[i]] + w[i])//判断是否变得更短
			{
				dis[v[i]] = dis[u[i]] + w[i];//更短的话进行松弛
				if (book[v[i]] == false)//被松弛的顶点入队
				{
					queue[tail++] = v[i];
					book[v[i]] = true;
				}
			}
		}
	}

	book[head] = false;
	head++;//出队
}