首页 > 编程语言 >AcWing算法基础课笔记——求最短路算法

AcWing算法基础课笔记——求最短路算法

时间：2024-06-09 22:29:13浏览次数：19  
标签：dist int 短路 d% st 算法 基础课 return AcWing

目录

朴素dijkstra算法 —— 模板题 AcWing 849. Dijkstra求最短路 I

时间复杂是 O(n2+m)O(n2+m), nn 表示点数，mm 表示边数

int g[N][N];  // 存储每条边
int dist[N];  // 存储1号点到每个点的最短距离
bool st[N];   // 存储每个点的最短路是否已经确定

// 求1号点到n号点的最短路，如果不存在则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < n - 1; i ++ )
    {
        int t = -1;     // 在还未确定最短路的点中，寻找距离最小的点
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
    
        // 用t更新其他点的距离
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);
    
        st[t] = true;
    }
    
    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];

}

题目代码

#include<iostream>
#include<cstring>
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);
	dist[1] = 0;
	
	for(int i = 0; i < n; i ++ ) {
		int t = -1;
		for(int j = 1; j <= n; j ++ ) {
			if(!st[j] && (t == -1 || dist[t] > dist[j])) {
				t = j;
			}
		}
		st[t] = true;
		
		for(int j = 1; j <= n; j ++) {
			dist[j] = min(dist[j], dist[t] + g[t][j]);
		}
	}
	
	if(dist[n] == 0x3f3f3f) return -1;
	return dist[n];
}

int main() {
	scanf("%d%d", &n, &m);
	
	memset(g, 0x3f, sizeof g);
	
	while(m --) {
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		g[a][b] = min(g[a][b], c);
		
	}
	
	int t = dijkstra();
	
	printf("%d\n", t);
	return 0;
}

堆优化版dijkstra —— 模板题 AcWing 850. Dijkstra求最短路 II

时间复杂度 O(mlogn)O(mlogn), nn 表示点数，mm 表示边数

typedef pair<int, int> PII;

int n;      // 点的数量
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储所有点到1号点的距离
bool st[N];     // 存储每个点的最短距离是否已确定

// 求1号点到n号点的最短距离，如果不存在，则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});      // first存储距离，second存储节点编号

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();
    
        int ver = t.second, distance = t.first;
    
        if (st[ver]) continue;
        st[ver] = true;
    
        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];
                heap.push({dist[j], j});
            }
        }
    }
    
    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];

}

题目代码

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N = 510;
typedef pair <int, int> PII;

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, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

int dijkstra(){
	memset(dist, 0x3f, sizeof dist);
	dist[1] = 0;
	
	priority_queue<PII, vector<PII>, greater<PII> > heap;
	heap.push({0, 1});
	
	while(heap.size()) {
		PII t = heap.top();
		heap.pop();
		
		int ver = t.second, distance = t.first;
		if(st[ver]) continue;
		st[ver] = true;
		
		for(int i = h[ver]; i != -1; i ++ ) {
			int j = e[i];
			if(dist[j] > distance + w[i]) {
				dist[j] = distance + w[i];
				heap.push({dist[j], j});
			}
		}
	}
	
	if(dist[n] == 0x3f3f3f3f) return -1;
	return dist[n];
}

int main() {
	scanf("%d%d", &n, &m);
	
	memset(h, -1, sizeof h);
	
	while(m --) {
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		add(a, b, c);
		
	}
	
	int t = dijkstra();
	
	printf("%d\n", t);
	return 0;
}

Bellman-Ford算法 —— 模板题 AcWing 853. 有边数限制的最短路

时间复杂度 O(nm)O(nm), nn 表示点数，mm 表示边数
注意在模板题中需要对下面的模板稍作修改，加上备份数组，详情见模板题。

int n, m;       // n表示点数，m表示边数
int dist[N];        // dist[x]存储1到x的最短路距离

struct Edge     // 边，a表示出点，b表示入点，w表示边的权重
{
    int a, b, w;
}edges[M];

// 求1到n的最短路距离，如果无法从1走到n，则返回-1。
int bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    // 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
    for (int i = 0; i < n; i ++ )
    {
        for (int j = 0; j < m; j ++ )
        {
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            if (dist[b] > dist[a] + w)
                dist[b] = dist[a] + w;
        }
    }
    
    if (dist[n] > 0x3f3f3f3f / 2) return -1;
    return dist[n];

}

题目代码

#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 510, M = 10010;

int n, m, k;

int dist[N], backup[N];

struct Edge {
	int a, b, w;
}edges[M];

int bellman_ford() {
	memset(dist, 0x3f, sizeof dist);
	dist[1] = 0; 
	
	for(int i = 0; i < k; i ++) {
		memcpy(backup, dist, sizeof dist);
		for(int j = 0; j < m; j ++ ) {
			int a = edges[j].a, b = edges[j].b, w = edges[j].w;
			dist[b] = min(dist[b], backup[a] + w);
		}
	}
	
	if(dist[n] > 0x3f3f3f3f / 2) return -1;
	return dist[n];
}

int main() {
	scanf("%d%d%d", &n, &m, &k);
	
	for(int i = 0; i < m; i ++ ) {
		int a, b, w;
		scanf("%d%d%d", &a, &b, &w);
		edges[i] = {a, b, w};
	}
	
	int t = bellman_ford();
	
	if(t == -1) puts("impossible");
	
	else printf("%d\n", t);
	
	return 0;
}

spfa 算法（队列优化的Bellman-Ford算法） —— 模板题 AcWing 851. spfa求最短路

时间复杂度 平均情况下 O(m)O(m)，最坏情况下 O(nm)O(nm), nn 表示点数，mm 表示边数

int n;      // 总点数
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储每个点到1号点的最短距离
bool st[N];     // 存储每个点是否在队列中

// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    queue<int> q;
    q.push(1);
    st[1] = true;
    
    while (q.size())
    {
        auto t = q.front();
        q.pop();
    
        st[t] = false;
    
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])     // 如果队列中已存在j，则不需要将j重复插入
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    
    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];

}

题目代码

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;

typedef pair<int, int> PII;

const int N = 100010;

int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool st[N]; //是否在队列中 

void add(int a, int b, int c) {
	e[idx] = b;
	w[idx] = c;
	ne[idx] = h[a];
	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[j] > dist[t] + w[i]) {
				dist[j] = dist[t] + w[i];
				if(!st[j]) {
					q.push(j);
					st[j] = true;
				}
			}
		}
	}
	
	if(dist[n] == 0x3f3f3f3f) return -1;
	return dist[n];
}

int main(){
	scanf("%d%d", &n, &m);
	
	memset(h, -1, sizeof h);
	
	while(m --) {
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		add(a, b, c);
	}
	
	int t = spfa();
	
	if(t == -1) puts("impossible");
	else printf("%d\n", t);
	
	return 0;
}

spfa判断图中是否存在负环 —— 模板题 AcWing 852. spfa判断负环

时间复杂度是 O(nm)O(nm), nn 表示点数，mm 表示边数

int n;      // 总点数
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N], cnt[N];        // dist[x]存储1号点到x的最短距离，cnt[x]存储1到x的最短路中经过的点数
bool st[N];     // 存储每个点是否在队列中

// 如果存在负环，则返回true，否则返回false。
bool spfa()
{
    // 不需要初始化dist数组
    // 原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点，由抽屉原理一定有两个点相同，所以存在环。

    queue<int> q;
    for (int i = 1; i <= n; i ++ )
    {
        q.push(i);
        st[i] = true;
    }
    
    while (q.size())
    {
        auto t = q.front();
        q.pop();
    
        st[t] = false;
    
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n) return true;       // 如果从1号点到x的最短路中包含至少n个点（不包括自己），则说明存在环
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    
    return false;

}

floyd算法 —— 模板题 AcWing 854. Floyd求最短路

时间复杂度是 O(n3)O(n3), nn 表示点数
初始化：

    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;

// 算法结束后，d[a][b]表示a到b的最短距离
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]);
}

题目代码

#include<iostream>
using namespace std;
const int N = 210, INF = 1e9;

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 a, b, w;
		scanf("%d%d%d", &a, &b, &w);
		
		d[a][b] = min(d[a][b], w);
	}
	
	floyd();
	
	while(Q--) {
		int a, b;
		scanf("%d%d", &a, &b);
		if(d[a][b] > INF / 2) puts("impossible");
		else{
			printf("%d\n", d[a][b]);
		}
	}
	
	return 0;
}

标签：dist,int,短路,d%,st,算法,基础课,return,AcWing
From： https://blog.csdn.net/Sophia2021XJTU/article/details/139567230

相关文章

  • （算法）判断是否互为字符重排——＜哈希表＞
    1.题⽬链接：⾯试01.02.判定是否互为字符重排2.题⽬描述：3.解法（哈希表）： 算法思路： 1.当两个字符串的⻓度不相等的时候，是不可能构成互相重排的，直接返回false；2.如果两个字符串能够构成互相重排，那么每个字符串中「各个字符」出现的「次数」⼀定是相同的。因此，我们可以......
  • 程序分享--常见算法/编程面试题：最长公共前缀
    关注我，持续分享逻辑思维&管理思维&面试题；可提供大厂面试辅导、及定制化求职/在职/管理/架构辅导；推荐专栏《10天学会使用asp.net编程AI大模型》，目前已完成所有内容，持续上传中。一顿烧烤不到的费用，让人能紧跟时代的浪潮。从普通网站，到公众号、小程序，再到AI大模型网站。干货满满......
  • TypeScript算法每日一题：最富有客户的资产总量（1672）
    作者：前端小王hs阿里云社区博客专家/清华大学出版社签约作者✍/CSDN百万访问博主/B站千粉前端up主题库：力扣题目序号：1672（简单）题目：最富有客户的资产总量给你一个mxn的整数网格accounts，其中accounts[i][j]是第i​​​​​​​​​​​​位客户在第j家银行托管的资产数......
  • 代码随想录算法训练营第十四天|二叉树递归遍历、迭代遍历、统一迭代
    二叉树遍历二叉树主要有两种遍历方式：深度优先遍历：先往深走，遇到叶子节点再往回走。深度优先遍历又分：前序遍历（中、左、右）中序遍历（左、中、右）后序遍历（左、右、中）广度优先遍历：一层一层的去遍历。（后面讲）递归遍历递归三要素确定递归函数的参数和返回值：确定哪些参数是递......
  • 模拟退火（Simulated Annealing, SA）算法是
    模拟退火（SimulatedAnnealing,SA）算法是一种概率型启发式搜索算法，用于寻找优化问题中的全局最优解。它受到冶金学中退火过程的启发，通过模拟金属冷却过程中的退火过程来寻找问题的最优解。以下是使用MATLAB实现模拟退火算法的一个简单示例。这个例子中，我们将使用模拟退火算法来......
  • 单链表相关面试算法题汇总
    技巧汇总快慢指针先找到中间节点如果要调用next..确保当前节点不为空。依次类推。.next不为空是否有环。走过的路。重新走。互相走。画图，分解，暴力法。用hashset插入法翻转。packagemainimport( "fmt" ."github.com/isdamir/gotype")funcAddLNode(h1,h2*L......
  • LeetCode 算法：除自身以外数组的乘积c++
    原题链接......
  • 【数据结构·队列】链队列（带头结点）模板简单应用算法设计：长整数加法计算
    目的：使用C++模板设计链队列的抽象数据类型（ADT）。并在此基础上，使用链队列ADT的基本操作，设计并实现简单应用的算法设计。内容：（1）请参照单链表的ADT模板，设计链队列的抽象数据类型。（由于该环境目前仅支持单文件的编译，故将所有内容都集中在一个源文件内。在实际的设计中，推荐将抽象类及......
  • 基于OpenCV的SIFT算法实现图像拼接(全景图像）
    一、SIFT算法尺度不变特征转换(Scale-invariantfeaturetransform或SIFT)是一种机器视觉的算法用来侦测与描述影像中的局部性特征，它在空间尺度中寻找极值点，并提取出其位置、尺度、旋转不变数，此算法由DavidLowe在1999年所发表，2004年完善总结。SIFT算法的实质是在不同的尺度......
  • 基于粒子群算法优化BP神经网络的PID控制算法（Matlab代码实现)
     ......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99