单源最短路问题

susenyang / 2023-08-16 / 原文

Bellman-Ford 算法

例题

【模板】负环

原理

Bellman-Ford 算法的原理是重复遍历 \(n - 1\) 遍所有的边，对其进行松弛操作。

如果源点到终点的距离小于源点到起点与这条边的权值之和，那么源点到终点的距离就用这个更小的距离来替换。

核心代码：

if (dis[e[j].from] + e[j].value < dis[e[j].to] && dis[e[j].from] != 2147483647)
			{
				dis[e[j].to] = dis[e[j].from] + e[j].value;
			}

同时我们可以引入 check 这个变量，如果当前一轮松弛操作没有对任何一个点的距离产生变化，那么可以提前退出循环。

注意判断源点是否与当前边的起点连通（距离不是正无穷）

关于重复遍历 \(n - 1\) 遍

在第 \(1\) 遍对所有的边进行松弛操作后，得到的是源点最多经过 \(1\) 条边到达其他边的最短距离。

在第 \(2\) 遍对所有的边进行松弛操作后，得到的是源点最多经过 \(2\) 条边到达其他边的最短距离。

……

在第 \(n - 1\) 遍对所有的边进行松弛操作后，得到的是源点最多经过 \(n - 1\) 条边到达其他边的最短距离。

而从源点到达其他点的最短距离，至多经过 \(n - 1\) 条边（一共只有 \(n\) 个点）。

判断负环

负环：一条边权之和为负数的回路

如果在 \(n - 1\) 遍遍历之后仍然可以产生对某些点最短距离的变化，那么说明图中有负环存在 （因为存在负环的图中不存在最短路径）。

代码

//Bellman-ForD算法
#include <iostream>
using namespace std;
#define int long long
int n, m;//n表示图的点数，m表示图的边数
int dis[50050];//dis表示源点到其他点的距离
int s;
struct EDGE
{
	int from, to, value;//分别表示起点，终点，权值
}e[1000050];

void init()
{
	for (int i = 1; i <= 50000; i++)dis[i] = 2147483647;
	cin >> n >> m >> s;
	dis[s] = 0;//将顶点的距离设为0
	for (int i = 1; i <= m; i++)cin >> e[i].from >> e[i].to >> e[i].value;
	//存边
}

void solve()
{
	//遍历n - 1遍所有的边，对它们进行松弛操作
	for (int i = 1; i <= n - 1; i++)
	{
		int check = 1;//记录当前一轮松弛是否有变化，如果没有变化，则提前退出循环
		for (int j = 1; j <= m; j++)
		{
			if (dis[e[j].from] + e[j].value < dis[e[j].to] && dis[e[j].from] != 2147483647)
			{
				dis[e[j].to] = dis[e[j].from] + e[j].value;
				check = 0;
			}
		}
		if (check == 1)break;
	}
}

void output()
{
	for (int i = 1; i <= n; i++)cout << dis[i] << " ";
	cout << endl;
   	//输出源点到其他节点的最短距离
}

signed main()
{
	init();
	solve();
	output();
	return 0;
}

Dijkstra算法

例题

【模板】单源最短路（弱化版）

【模板】单源最短路（标准版）

原理

对于一个无负权边的图，可以使用上述算法，其类似于 Prim 算法。

设起点为 \(i\)，那么维护一个数组 dis[n]，其中的元素 dis[j] 表示 \(i\) 与 \(j\) 的最短路径
。
初始时，若 \(i\), \(j\) 不连通，则设 dis[j] 为无穷大。

首先遍历 dis[n] 数组，找到最小值，设为 dis[x0]，即 \(x_0\) 是与起点 \(i\) 连通的最小的边。

以 \(x_0\) 为中转点，遍历除 \(i\) 与 \(x_0\) 以外的点，求出起点 \(i\) 到它们的距离（\(i\) 到 \(x_0\) 的距离与 \(i\) 到其中某一点距离之和）。

如果以 \(x_0\) 为中转点， \(i\) 到某个点的距离小于原有的距离，那么用这个更小的距离更新原有的距离。

依此类推，每次都将中转点设为 没有被设为中转点过的且到起点距离最短的（dis[j] 最小）点。

直到所有点被遍历完。

核心代码

类似于 Bellman-Ford 算法终的松弛操作

不同点在于存图方式：Bellman-Ford 算法存储了每一条边的起点、终点和权值 （离散），Dijkstra 算法中使用了链式前向星存图方法 （连续）。

代码

#include <iostream>
using namespace std;
const int inf = 0x7fffffff;
int dis[10005];//ans代表到达i点的最小花费
bool vis[10005];//是否以某个点为中转点计算过
int head[500005];//以某一个点为起点的最后一条边的编号
int cnt = 0;

struct EDGE
{
	int next, to, w;
	//next上一条边的编号
	//to边的终点
	//w边的权重
}e[500005];

//存图方式：链式前向星
//实际上，通过head数组可以找到某个点最后一条边的编号
//然后通过next指向前一条边
//head[a] = i;表示以点a为起点的最后一条边的编号为i
//e[i]即表示这最后一条边
//e[i].next表示以a为起点的倒数第二条边

void addedge(int u, int v, int w, int s)
{
	cnt++;
	e[cnt].next = head[u];
	//前一条边的编号为head[u]
	e[cnt].to = v;
	e[cnt].w = w;
	head[u] = cnt;
	//更新以u为起点的最后一条边的编号
	if (u == s && w < dis[v])dis[v] = w;
}
void init(int n, int s, int m)
{
	for (int i = 1; i <= n; i++)dis[i] = inf;
	for (int u, v, w; m; m--)
	{
		cin >> u >> v >> w;
		addedge(u, v, w, s);
	}
	dis[s] = 0;
	vis[s] = 1;
}
bool isEnd(int n)
{
	for (int i = 1; i <= n; i++)if (vis[i] == 0)return 0;
	return 1;
}

int main()
{
	int n, m, s;
	cin >> n >> m >> s;
	init(n, s, m);

	int minn, mini;
	while (1)
	{
		minn = inf, mini = 0;
		for (int i = 1; i <= n; i++)
		{
			if (minn > dis[i] && vis[i] == 0)
			{
				minn = dis[i];
				mini = i;
			}
		}
		vis[mini] = 1;
		if (mini == 0)break;
		//以mini为新的中转点，遍历点mini所有的连通边
		for (int i = head[mini]; i != 0; i = e[i].next)//链式前向星存图方法，对某一起点的边的遍历,这里是对以点mini为起点的边的遍历
		{
			if (vis[e[i].to] == 0 && e[i].w + dis[mini] < dis[e[i].to])dis[e[i].to] = dis[mini] + e[i].w;
		}
	}
	for (int i = 1; i <= n; i++)cout << dis[i] << " ";
    		cout<<endl;
    		//输出源点到其他节点的最短距离
	return 0;
}