目录
有负权边的单源最短路(bellman-ford, spfa)
❓为什么Dijkstra不能使用在含负权的图中,而bellman-ford可以?
→spfa(对bellman-ford进行队列优化)(一定要求图中不含负环)
初学图论不久, 这个过程快乐而又痛苦, 大佬们的结论有的晦涩难懂, 又充斥着美感, 有的可能还未被广泛认可但依旧犀利, 在特定的问题上各有千秋, 怕什么真理无穷呢，进一寸有一寸的欢喜。
此文会持续补充...
DFS
BFS
树与图的广度优先遍历
https://blog.csdn.net/qq_39391544/article/details/120977766→拓扑排序
与图的广度优先遍历基本是一样的, 还增加了表示各个顶点入度的数组 in[ ],
1.把入度为零的点放入队列
2.不断循环下面的步骤
判断栈是否为空, 若空则循环结束,否则:
取出队头, 当删除该节点即相关的边时, 与其邻接的点入度减1, 如果此时入度为零了, 则放入队列
3.如果入过队的节点数比总结点数少, 则说明在图中必有环路
例题:
输入样例：
3 3
1 2
2 3
1 3
输出样例：
1 2 3#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int n, m;
int h[N], e[N], ne[N], idx;
int q[N]; //队列
int in[N]; //入度
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
bool topSort()
{
int front = -1, rear = -1;
for(int i = 1; i <= n; i ++)
if(!in[i])
q[++rear] = i;
while(front != rear)
{
int t = q[++front];
for(int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
in[j]--;
if(!in[j]){
q[++rear] = j;
}
}
}
return rear == n-1; //q中存的序列实际上就是拓扑序列
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
int a, b;
while (m -- )
{
scanf("%d%d", &a, &b);
add(a, b);
in[b] ++;
}
if(topSort()){
for(int i = 0; i < n; i ++) printf("%d ", q[i]);
}else{
cout << "-1";
}
return 0;
}最短路
单源最短路(朴素Dijkstra)(一定不能存在负权边)
→堆优化Dijkstra(待续...)
有负权边的单源最短路(bellman-ford, spfa)
→bellman-ford(有边数限制)
当进行第k次更新操作时,都能保证最短路径是从起点到各个点的移动少于k次的情况
假设 1 号点到 n 号点是可达的，每一个点同时向指向的方向出发，更新相邻的点的最短距离，通过循环 n-1 次操作，若图中不存在负环，则 1 号点一定会到达 n 号点，若图中存在负环，则在 n-1 次松弛后一定还会更新
bellman-ford与Dijkstra的异同
| Dijkstra | bellman-ford | |
| 同 | bellman-ford算法与Dijkstra类似，都以松弛操作为基础，即估计的最短路径值渐渐地被更加准确的值替代，直至得到最优解。在两个算法中，计算时每个边之间的估计距离值都比真实值大，并且被新找到路径的最小长度替代。 | |
| 异 | 以贪心法选取未被处理的具有最小权值的节点，然后对其的出边进行松弛操作 | 直接对所有边进行松弛操作，共n-1次(或是k次,及人为限定的边数)，其中n是图中点的数量。在重复的计算中，已计算得到正确的距离的边的数量不断增加，直到所有边都计算得到了正确的路径。这样的策略使得贝尔曼-福特算法比迪科斯彻算法适用于更多种类的输入。 |
❓为什么Dijkstra不能使用在含负权的图中,而bellman-ford可以?
引用AcWing小呆呆的解读
AcWing 853. 有边数限制的最短路 - AcWingAcWing,题解,有边数限制的最短路,
例题:
输入样例：
3 3 1
1 2 1
2 3 1
1 3 3
输出样例：
3for n次
for 所有边 a,b,w (松弛操作)
dist[b] = min(dist[b],back_dist[a] + w)
注意：
- back[ ] 数组是上一次迭代后 dist[] 数组的备份，由于每个点同时向外出发，因此需要对 dist[] 数组进行备份，若不进行备份会因此发生串联效应，会影响到下一个点
- INF是一个确定的值，并非真正的无穷大，会随着其他数值而受到影响，dist[n]大于某个与INF相同数量级的数即可 (我的理解再强的人也有软肋啊,但瘦死的骆驼比马大,即使遇上了负权小于INF了, 也是不容小觑的量级,也属于常人无法到达的境界)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510, M = 10010, INF = 0x3f3f3f3f;
struct Edge{
int a, b, w;
}e[M];
int n,m,k;
int dist[N], back_dist[N];//最短距离
void bellman_ford()
{
memset(dist, 0x3f, sizeof dist);//☆记得初始化
dist[1] = 0;
for(int i = 0; i < k; i++)
{
memcpy(back_dist, dist, sizeof dist);//记住上一次的状态
for(int j = 0; j < m; j++)
{
int a = e[j].a, b = e[j].b, w = e[j].w;
dist[b] = min(dist[b], back_dist[a]+w);//这里需要用back_dist来更新
}
}
}
int main()
{
cin >> n >> m >> k;
int a,b,w;
for(int i = 0; i < m; i++)
{
scanf("%d%d%d", &a, &b, &w);
e[i] = {a, b, w};
}
bellman_ford();
if(dist[n] > INF/2) cout << "impossible";
else cout << dist[n];
return 0;
}
→spfa(对bellman-ford进行队列优化)(一定要求图中不含负环)
分析贝尔曼福特的这一步dist[b] = min(dist[b],back[a] + w), 我们什么时候需要更新dist[b]呢? 是的,只有当back_dist[a] 变小的时候,才需要, (前人栽树后人乘凉),根据这一点我们利用队列进行优化操作, 队列里存的是待更新的点,与宽搜很相似
851. spfa求最短路 - AcWing题库高质量的算法题库
输入样例：
3 3
1 2 5
2 3 -3
1 3 4
输出样例：
2#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10, INF = 0x3f3f3f3f;
int n,m;
int h[N],e[N],ne[N],w[N],idx;
int dist[N];
bool st[N];
void add(int a, int b, int c)
{
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}
int spfa()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
queue<int > q;
q.push(1);
st[1] = true;
while(q.size())
{
int t = q.front();
q.pop();
st[t] = false;
for(int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if(dist[t]+w[i] < dist[j]){
dist[j] = dist[t]+w[i];
if(!st[j]) //是否已在队列中
{
st[j] = true;
q.push(j);
}
}
}
}
return dist[n];
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
int a, b, c;
for (int i = 0; i < m; i ++ )
{
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
int res = spfa();
if(res==INF) cout << "impossible";
else cout << res;
return 0;
}spfa判断负环(待续...)
多源最短路Floyd
基于动态规划, 从i到j的最短距离为 d[i, j] = min{d[i, j], d[i, k]+d[k, j]}, 从整体上看, 我们所要做的很简单,就是穷举所有情况(1 ≤ i , j ,k ≤ n)
输入样例：
3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3
输出样例：
impossible
1#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 210, INF = 0x3f3f3f3f;
int n, m, k;
int d[N][N];
void floyd()
{
for (int k = 1; k <= n; k ++ )
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
int main()
{
cin >> n >> m >> k;
memset(d, 0x3f, sizeof d);
for (int i = 1; i <= n; i ++ ) d[i][i] = 0;
int a, b, c;
while (m -- )
{
scanf("%d%d%d", &a, &b, &c);
d[a][b] = min(d[a][b], c);
}
floyd();
while (k --)
{
scanf("%d%d", &a, &b);
int res = d[a][b];
if (res > INF/2) cout << "impossible" << '\n';
else cout << res << '\n';
}
return 0;
}