-
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;
}