小蓝xlanll

这个屌丝很懒，什么也没留下！

热门标签

图论之最短路问题（acwing模板篇）_图论最短路样例

作者：小蓝xlanll | 2024-03-15 18:22:16

踩

图论最短路样例

Bellman-Ford算法（处理有负权边的图）

例题：有边数限制的最短路

spfa算法（Bellman-Ford算法的队列优化算法）

spfa求负环

Floyd算法（多源最短路）

名词解释：n：通常代表点数 m：通常代表边数

源：起点单源：一个起点多源：多个起点

汇点：终点

入度：有多少条边指向我

出度：以这个点为起点出去的边数

边权：离散数学或数据结构中，图的每条边上带的一个数值，他代表的含义可以是长度等等，这个值就是边权

框架图：

朴素的Dijkstra算法：

由于它的时间复杂度是O（N^2）边数与时间复杂度无关，所以它适合做稠密图

稠密图：边数是点数的2~3倍

ACwing算法基础课全程笔记（2021年8月12日开始重写+优化）_hebtu_Kangweiqi的博客-CSDN博客_acwing笔记算法基础课笔记，请支持正版https://blog.csdn.net/hebtu_Kangweiqi/article/details/109124329借用大佬的图= =

Dijkstra模板：

例题：Dijkstra求最短路

给定一个n个点m条边的有向图，图中可能存在重边和自环，所有边权均为正值。

请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出-1

思路解析：有贪心的感觉，每次我都选择离我距离最小的那条走，然后最1~j的最短距离就变成

1~t点的距离 t~j的最短距离

建议自己看着代码自己在图上模拟一下，会感受到这个算法之妙！！！


#include<iostream>
using namespace std;
const int N = 510;
int n, m;
int g[N][N];//采用邻接矩阵存储
int dist[N];//距离数组
bool st[N];//判断数组
int dijkstra() 
{
    memset(dist, 0x3f, sizeof dist);//初始化数组的值为一个很大的数1e9
    dist[1] = 0;//将第1号点的到自身的距离初始化为0
    for (int i = 0; i < n; i++) 
    {//n次迭代
        int t = -1;//随便的一个没有意义的数即可：目的是下面的寻找出2~n内距离点1最小的数
        for (int j = 1; j <= n; j++)//从1开始遍历：注意这个细节
        {
            if (!st[j] && (t == -1 || dist[j] < dist[t]))//如果该点未被走过
            {
                t = j;//相当于寻找最小值  1~1  1~2
            }
        }
        st[t] = 1;//标记已经用过了这个点
        for (int j = 1; j <= n; j++)//遍历1号点到n号点
        {//更新距离
            dist[j] = min(dist[j], dist[t] + g[t][j]);//1~j点的距离变为了：1~t的距离+t~j的距离
        }
    }
    if (dist[n] == 0x3f3f3f3f) return -1;//如果n点数组没有被用到过，那么证明走不到n点
    else return dist[n];
}
int main() {
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
    while (m--)
    {
        int x, y, z;//x~y的距离为 z
        cin >> x >> y >> z;
        g[x][y] = min(g[x][y], z);
    }
    int t = dijkstra();
    printf("%d\n", t);
    return 0;
}

堆优化的dijkstra算法

通过对上图的分析：我们可以对2的（1）（3）用堆进行优化从而降低时间复杂度，但是会引入边数这个变量，所以堆优化版的dijkstra版适合做稀疏图

例题：Dijkstra求最短路Ⅱ

问题：

给定一个n个点m条边的有向图，图中可能存在重边和自环，所有边权均为非负值。

请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出-1。

针对稀疏图，我们采用邻接表法

代码实现：


#include<iostream>
#include <queue>
using namespace std;
 
const int N = 1e6 + 10;
typedef pair<int, int> PII;
int h[N], e[2 * N], ne[2 * N], w[N], idx;//邻接表+权重数组
int n, m;//点数+边数 
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 dijkstra() 
{
	memset(dist, 0x3f, sizeof dist);//初始化距离为一个很大的数
	dist[1] = 0;//1到自身的距离为0
	priority_queue<PII, vector<PII>, greater<PII> >heap;//建立小根堆（优先队列）
	heap.push({ 0,1 });//入堆
	while (heap.size())//当队列不为空
	{
		auto t = heap.top();//取头
		heap.pop();//删头
		int ver = t.second, distance = t.first;//first：距离，ver：节点数
		if (st[ver]) continue;//如果已经标记过的节点，则不走
		st[ver] = 1;//标记节点
		for (int i = h[ver]; i != -1; i = ne[i])//邻接表的遍历 
		{
			int j = e[i];//获取节点数
			if (dist[j] > distance + w[i])//求最小距离
			{
				dist[j] = distance + w[i];//节点1的到节点j的距离就是头节点的距离+它存的权重（边长）
				heap.push({ dist[j],j });//入堆
			}
		}
	}
	if (dist[n] == 0x3f3f3f3f) return -1;
	return dist[n];
}
int main() {
	cin >> n >> m;
	memset(h, -1, sizeof h);
	while (m--) 
	{
		int x, y, z;
		cin >> x >> y >> z;
		add(x, y, z);
	}
	cout << dijkstra();
}

Bellman-Ford算法（处理有负权边的图）

1、什么是bellman - ford算法？
Bellman - ford算法是求含负权图的单源最短路径的一种算法，效率较低，代码难度较小。其原理为连续进行松弛，在每次松弛时把每条边都更新一下，若在n-1次松弛后还能更新，则说明图中有负环，因此无法得出结果，否则就完成。
(通俗的来讲就是：假设1号点到n号点是可达的，每一个点同时向指向的方向出发，更新相邻的点的最短距离，通过循环n-1次操作，若图中不存在负环，则1号点一定会到达n号点，若图中存在负环，则在n-1次松弛后一定还会更新)

2、bellman - ford算法的具体步骤
for n次
for 所有边 a,b,w (松弛操作)
dist[b] = min(dist[b],back[a] + w)

注意：back[]数组是上一次迭代后dist[]数组的备份，由于是每个点同时向外出发，因此需要对dist[]数组进行备份，若不进行备份会因此发生串联效应，影响到下一个点

3、在下面代码中，是否能到达n号点的判断中需要进行if(dist[n] > INF/2)判断，而并非是if(dist[n] == INF)判断，原因是INF是一个确定的值，并非真正的无穷大，会随着其他数值而受到影响，dist[n]大于某个与INF相同数量级的数即可

4、bellman - ford算法擅长解决有边数限制的最短路问题
时间复杂度 O ( n m ) O(nm)O(nm)
其中n为点数，m为边数
————————————————
版权声明：本文为CSDN博主「云算法」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/hebtu_Kangweiqi/article/details/109124329

例题：有边数限制的最短路

问题：

给定一个n个点m条边的有向图，图中可能存在重边和自环，边权可能为负数。

请你求出从1号点到n号点的最多经过k条边的最短距离，如果无法从1号点走到n号点，输出impossible 注意：图中可能 存在负权回路


#include <iostream>
#include <cstring>
 
using namespace std;
 
const int N = 1e4 + 50;
 
int n, m, k;
int dis[N], backup[N];
 
struct edge { int a, b, w; } e[N];
 
void bellman()
{
    memset(dis, 0x3f, sizeof dis);
    dis[1] = 0;
    
    for (int i = 0; i < k; i ++)//最多经过 k 条边
    {
        memcpy(backup, dis, sizeof dis);//每次用上一次的状态去更新
        for (int j = 1; j <= m; j ++)
        {
            int a = e[j].a, b = e[j].b, w = e[j].w;
            dis[b] = min(dis[b], backup[a] + w);//到b点的距离相当于a点的距离加上边长
        }
    }
}
 
int main()
{
    cin >> n >> m >> k;
    
    for (int i = 1; i <= m; i ++)
        cin >> e[i].a >> e[i].b >> e[i].w;
    
    bellman();
    //是否能到达n号点的判断中需要进行if(dist[n] > INF/2)判断，而并非是if(dist[n] == INF)判断，原因是INF是一个确定的值，并非真正的无穷大，会随着其他数值而受到影响，dist[n]大于某个与INF相同数量级的数即可
    if (dis[n] > 0x3f3f3f3f / 2) puts("impossible");
    else cout << dis[n] << endl;
    
    return 0;
}

spfa算法（Bellman-Ford算法的队列优化算法）


spfa算法步骤
queue <– 1
while queue 不为空
(1) t <– 队头
queue.pop()
(2)用 t 更新所有出边 t –> b，权值为w
queue <– b (若该点被更新过，则拿该点更新其他点)

时间复杂度一般：O ( m ) 最坏：O ( n m )
n为点数，m为边数

3、spfa也能解决权值为正的图的最短距离问题，且一般情况下比Dijkstra算法还好
————————————————
版权声明：本文为CSDN博主「云算法」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/hebtu_Kangweiqi/article/details/109124329

问题：

有边数限制的最短路

给定一个n个点m条边的有向图，图中可能存在重边和自环，边权可能为负数。

请你求出从1号点到n号点的最多经过k条边的最短距离，如果无法从1号点走到n号点，输出impossible。

注意：图中可能存在负权回路。


#include<iostream>
#include<queue>
using namespace std;
 
const int N = 1e5 + 5;
int n, m, dis[N];
bool st[N];//代表点是否在队列中
int h[N], e[N], ne[N], w[N], idx;//单链表
void add(int a, int b, int c)//单链表的插入操作
{
	e[idx] = b; 
	ne[idx] = h[a]; 
	w[idx] = c; 
	h[a] = idx++;
}
int spfa() 
{
	queue<int> q;
	memset(dis, 0x3f, sizeof dis);
	q.push(1);//放入节点1
	dis[1] = 0;//距离为1
	st[1] = 1;//判断
	while (!q.empty()) //队列不为空
	{
		int u = q.front();//取出头
		q.pop();//删头
		st[u] = 0;//标记
		for (int i = h[u]; i != -1; i = ne[i])//遍历链表
		{
			int v = e[i];//取出节点
			if (dis[v] > dis[u] + w[i])//求最小值 
			{
				dis[v] = dis[u] + w[i];
				if (!st[v]) //如果没有走过
				{
					q.push(v);//放入
					st[v] = 1;//标记
				}
			}
		}
	}
	if (dis[n] == 0x3f3f3f3f) return -1;
	else return dis[n];
}
int main() {
	memset(h, -1, sizeof h);
	scanf("%d%d", &n, &m);
	while (m--) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		add(x, y, z);
	}
	int t = spfa();
	if (t == -1) puts("impossible");
	else printf("%d", t);
}

spfa求负环

问题：

给定一个n个点m条边的有向图，图中可能存在重边和自环，边权可能为负数

请你判断图中是否存在负权回路


#include<iostream>
#include<queue>
using namespace std;
const int N = 2005, M = 10005;
int h[N], e[M], ne[M], w[M], idx, n, m;
int dis[N], cnt[N];//需要额外一个cnt数组，记录当前点最短路上的边数
bool st[N];
void add(int a, int b, int c) 
{
	e[idx] = b; 
	w[idx] = c; 
	ne[idx] = h[a];
	h[a] = idx++;
}
bool spfa() 
{
	/*首先距离不需要初始化*/
	queue<int> q;
	/*将所有点入队，可以防止有的点不能走到负环*/
	for (int i = 1; i <= n; i++) 
	{
		q.push(i);
		st[i] = 1;
	}
	while (!q.empty()) 
	{
		int u = q.front();
		q.pop();
		st[u] = 0;
		for (int i = h[u]; i != -1; i = ne[i]) 
		{
			int v = e[i];
			if (dis[v] > dis[u] + w[i]) 
			{
				dis[v] = dis[u] + w[i];
				cnt[v] = cnt[u] + 1;
				if (cnt[v] >= n) return 1;
				/*如果超过n，根据抽屉原理，中间经过的点数一定大于n，*/
				if (!st[v]) {
					q.push(v);
					st[v] = 1;
				}
			}
		}
	}
	return 0;
}
int main() {
	scanf("%d%d", &n, &m);
	memset(h, -1, sizeof h);
	for (int i = 0; i < m; i++) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		add(x, y, z);
	}
	if (spfa()) puts("Yes");
	else puts("No");
}

Floyd算法（多源最短路）

问题：

给定一个n个点m条边的有向图，图中可能存在重边和自环，边权可能为负数。

再给定k个询问，每个询问包含两个整数x和y，表示查询从点x到点y的最短距离，如果路径不存在，则输出“impossible”。

数据保证图中不存在负权回路


#include<iostream>
using namespace std;
const int N = 210;
const int inf = 0x3f3f3f3f;
int n, m, q;
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() {
	scanf("%d%d%d", &n, &m, &q);
	/*初始化*/
	for (int i = 1; i <= n; i++) 
	{
		for (int j = 1; j <= n; j++) 
		{
			if (i == j) d[i][j] = 0;
			else d[i][j] = inf;
		}
	}
 
	while (m--)
	{
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		d[x][y] = min(d[x][y], z);//注意重边
	}
	floyd();
	while (q--) //q次询问
	{
		int x, y;
		scanf("%d%d", &x, &y);
		if (d[x][y] > inf / 2) puts("impossible");//题目可能会出现负权边，所以还要应用之前的套路
		else printf("%d\n", d[x][y]);
	}
	return 0;
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小蓝xlanll/article/detail/243580