搜索与图论第六期 最短路问题


前言

最短路问题真的很重要很重要希望大家都能够完全掌握所有最短路算法!!

一、最短路问题的分类

Dijkstra:


Dijkstra算法是一种著名的图算法,主要用于求解有权图中的单源最短路径问题。它由荷兰计算机科学家艾兹赫尔·戴克斯特拉(Edsger Wybe Dijkstra)在1956年首次提出。Dijkstra算法的核心思想是通过以下步骤逐步构建最短路径树:

初始化:创建一个空白的最短路径字典,其中每个节点的距离设置为无穷大,起始节点的距离设置为0。
标记已访问节点:创建一个已访问节点集合,并将所有节点都加入这个集合。
更新距离:对于未被访问的节点,从其未被访问的邻居中选择距离当前节点最近的邻居,将其标记为已访问,并且更新该邻居节点的距离。
重复上述步骤:直到所有节点都被访问,此时已经得到了从起始节点到所有其他节点的最短路径。
Dijkstra算法的特点在于它能够处理图中的负权边,但通常会忽略这些边,因为它们不会影响最终的路径长度计算。如果图中存在负权边,可能需要使用其他的图算法,如Bellman-Ford算法。此外,Dijkstra算法的时间复杂度通常是O(V^2),其中V是节点数量,但如果使用优先队列来优化,时间复杂度可以减少到O(Elog(V)),其中E是边数。1

在实际编程实现时,可以使用不同的数据结构和算法来实现Dijkstra算法,以提高效率。例如,可以使用优先队列或堆来加速松弛操作,从而减少总体时间复杂度。2

总结一下,Dijkstra算法的主要优点是可以有效地解决单源最短路径问题,并且在大多数情况下不需要考虑负权边的影响。它在多个领域有着广泛的应用,包括路线规划、网络路由、资源分配等。

Bellman-Ford算法:

贝尔曼-福特算法(Bellman-Ford Algorithm)是一种用于求解单源最短路径问题的算法,由理查德·贝尔曼(Richard Bellman)和莱斯特·福特(Lester Ford)共同创立。该算法能够处理图中的负权边,并具有简单的实现方式和较高的时间复杂度。贝尔曼-福特算法的核心思想是通过多次松弛操作来确定所有可能的最短路径。每次迭代中,算法会更新所有节点的距离,确保它们符合“三角不等式”,即任意两点间的距离加上第三者的重量小于或等于这两点间距离之和。

尽管贝尔曼-福特算法在处理带负权边的最短路径问题上表现良好,但在某些情况下可能会遇到困难,如当图中存在负权环路时,可能会导致无法找到任何有效的最短路径。此外,虽然它可以处理负权边,但其时间复杂度为 \( O(VE) \),其中 \( V \) 是顶点的数量,\( E \) 是边的数量,这使得它在实践中可能不是最佳选择。

总结来说,贝尔曼-福特算法的主要优点包括支持负权边和简单性,而其主要缺点在于高的时间复杂度。为了提高效率,算法可以进行一些优化措施。需要注意的是,贝尔曼-福特算法有时也被称作 Moore-Bellman-Ford 算法,因为它还涉及到了另一位科学家 Edward F. Moore 的贡献。

SPFA算法:

SPFA算法
SPFA 算法是 Bellman-Ford算法 的队列优化算法的别称,通常用于求含负权边的单源最短路径,以及判负权环

Floyd算法:

floyd算法
Floyd算法,也被称为弗洛伊德算法或插点法,是一种解决加权图中顶点间最短路径问题的算法。它可以处理有向图或负权图(但不能存在负权回路),并同时用于计算有向图的传递闭包。Floyd算法的名称来源于其创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德。

Floyd算法的核心思想是利用动态规划技术来构建一个路径矩阵,这个矩阵包含了图中所有顶点对之间的最短路径长度。算法的基本步骤包括初始化路径矩阵、进行多次更新操作以及最终获取任意两点之间的最短路径。

具体来说,算法会创建两个矩阵:一个存储了顶点对之间的距离,另一个存储了这些距离的逆。在每一次迭代中,都会根据已有的信息更新这两个矩阵。这个过程涉及到多个嵌套的for循环,直到所有的路径都被计算出来为止。

Floyd算法的时间复杂度和空间复杂度分别为O(n^3)和O(n^2),这意味着它在处理大规模网络图时会比较耗时。此外,虽然算法本身不需要回溯路径的具体信息,但它确实可以用来构造出最短路径的详细列表。

总结一下,Floyd算法的主要特点和应用场景如下:

适用范围:适用于有向图或负权图,不能有负权回路。
时间复杂度:O(n^3),即n³次操作。
空间复杂度:O(n^2),即n²个变量。
主要用途:求解任意两点间的最短路径,也可以用于计算传递闭包。
其他应用:在某些情况下,可以用于查找关系的传递闭包。

二、例题

1.朴素Dijkstra:


AC代码:

#include<bits/stdc++.h>

using namespace std;

const int N = 510;
int g[N][N];
int dis[N];
bool st[N];
int n,m;
int dij()
{
	memset(dis,0x3f,sizeof dis);
	dis[1] = 0;
	for(int i=0;i<n;i++){
		int t = -1;
		for(int j=1;j<=n;j++){
			if(!st[j] && (t==-1 || dis[t]>dis[j]))
				t=j;
		}
		st[t] = true;
		for(int j=1;j <= n;j++){
			dis[j] = min(dis[t]+g[t][j],dis[j]);
		}
	}
	if(dis[n] == 0x3f3f3f3f) return -1;
	return dis[n];
}
int main()
{
    cin>>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 = dij();
	cout<<t<<endl;
	return 0;
}

2、堆优化Dijkstra:

AC代码:

#include<bits/stdc++.h>

using namespace std;

const int N = 15e4+10; 
typedef pair<int ,int>PII;
int h[N],e[N],ne[N],idx,w[N];
int n,m;
int dis[N],st[N];
void add(int a,int b,int c)
{
	e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx ++;
}

int dij()
{
	memset(dis,0x3f,sizeof dis);
	dis[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;
		if(st[ver]) continue;
		st[ver] = true;
		for(int i=h[ver];i!=-1;i= ne[i]){
			int j = e[i];//为了更新其他的边
			if(dis[j] > w[i] + dis[ver] && !st[j]){
				dis[j]  =w[i]+ dis[ver];
				heap.push({dis[j],j});
			}
		}
	}
	if(dis[n] == 0x3f3f3f3f ) return -1;
	return dis[n];
}
int main()
{
	cin>>n>>m;
	memset(h,-1,sizeof h);
	while(m--){
		int a,b,c;
		cin>>a>>b>>c;
		add(a,b,c);
	}
	cout<<dij()<<endl;
	return 0;
}

3、 有边数限制的最短路:

AC代码:

#include<bits/stdc++.h>

using namespace std;

const int N = 520,M = 10010;
int n,m,k;
int dis[N],backup[M];

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

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

4、spfa判断负环:

AC代码:

#include<bits/stdc++.h>

using namespace std;

const int N = 15e4+10; 
typedef pair<int ,int>PII;
int h[N],e[N],ne[N],idx,w[N];
int n,m;
int dis[N],st[N],cnt[N];
void add(int a,int b,int c)
{
	e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx ++;
}

int spfa()
{
	dis[1] = 0;
	queue<int>q;
	for(int i=1;i<=n;i++){
		st[i]= true;
		q.push(i);
	}
	
	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(dis[j] > dis[t] + w[i]){
				dis[j] = dis[t]+w[i];
				cnt[j] = cnt[t] + 1;
				if(cnt[j]>=n) return true; 
				q.push(j);
				st[j] = true;
			}
		}
	}
	return false;
}
int main()
{
	cin>>n>>m;
	memset(h,-1,sizeof h);
	while(m--){
		int a,b,c;
		cin>>a>>b>>c;
		add(a,b,c);
	}
	if(spfa()) puts("Yes");
	else puts("No");
	return 0;
}

5、spfa求最短路:

AC代码:

#include<bits/stdc++.h>

using namespace std;

const int N = 15e4+10; 
typedef pair<int ,int>PII;
int h[N],e[N],ne[N],idx,w[N];
int n,m;
int dis[N],st[N];
void add(int a,int b,int c)
{
	e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx ++;
}

int dij()
{
	memset(dis,0x3f,sizeof dis);
	dis[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(dis[j] > dis[t] + w[i]){
				dis[j] = dis[t]+w[i];
				q.push(j);
				st[j] = true;
			}
		}
	}
	if(dis[n] == 0x3f3f3f3f) return -1;
	return dis[n];
}
int main()
{
	cin>>n>>m;
	memset(h,-1,sizeof h);
	while(m--){
		int a,b,c;
		cin>>a>>b>>c;
		add(a,b,c);
	}
	int t = dij();
	if(t == -1) puts("impossible");
	else cout<<t<<endl;
	return 0;
}

6、Floyd求最短路:

AC代码:

#include<bits/stdc++.h>

using namespace std;

const int N = 210,INF= 1e9;

int n,m,q;
int d[N][N];
int main()
{
	cin>>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);
	}
	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]);
			}
		}
	}
	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;
}

总结:这部分真的特别特别的重要,希望大家能够完全掌握,对以后的面试也有帮助的,感谢大家的观看!!!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/341293.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

(十)Head first design patterns组合模式(c++)

组合模式 组合模式在参考链接中已经讲得很好了&#xff0c;这里只简单讲讲就好。 组合模式的意图是表达部分-整体层次结构。 当你需要管理一个组合对象&#xff0c;又要管理这个组合对象的单个对象。这个时候就可以让这个组合对象和单个对象继承同一个基类&#xff0c;以便用…

pytorch学习笔记(十一)

优化器学习 把搭建好的模型拿来训练&#xff0c;得到最优的参数。 import torch.optim import torchvision from torch import nn from torch.nn import Sequential, Conv2d, MaxPool2d, Flatten, Linear from torch.utils.data import DataLoaderdataset torchvision.datas…

E. Increasing Subsequences

Part1 寒假思维训练之每日一道构造题&#xff08;思维 构造 数学&#xff09;题目链接&#xff1a; Problem - E - Codeforces 题意&#xff1a; 给定一个整数&#xff0c;数字n的范围是&#xff0c;闭区间&#xff0c;要求构造一个递增子序列&#xff08;可以不连续&…

在Python环境中运行R语言的配环境实用教程

前情提要 在做一些生物信息与医学统计的工作&#xff0c;本来偷懒希望只靠python完成的&#xff0c;结果还是需要用R语言&#xff0c;倒腾了一会儿&#xff0c;调成功了&#xff0c;就记录一下这个过程。 我的环境&#xff1a; win10, pycharm, R-4.3.2 首先&#xff0c;我们…

proxy 代理的接口报错301问题

项目系统里仅仅这个接口报错&#xff0c;反向代理错误导致。 默认情况下&#xff0c;不接受运行在HTTPS上&#xff0c;且使用了无效证书的后端服务器。如果你想要接受&#xff0c;修改配置&#xff1a;secure: false&#xff08;简单意思&#xff1a;如果本地没有进行过https相…

Armv8-M的TrustZone技术之内存属性单元

如果处理器包含Armv8-M安全扩展&#xff0c;则内存区域的安全状态由内部安全属性单元&#xff08;SAU&#xff0c;Secure Attribution Unit&#xff09;或外部实现定义的属性单元&#xff08;IDAU&#xff0c;Implementation Defined Attribution Unit&#xff09;的组合控制。…

如何在 Ubuntu 22.04 上安装 Apache Web 服务器

前些天发现了一个人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;最重要的屌图甚多&#xff0c;忍不住分享一下给大家。点击跳转到网站。 如何在 Ubuntu 22.04 上安装 Apache Web 服务器 介绍 Apache HTTP 服务器是世界上使用最广泛的 Web 服务器。它…

苹果眼镜(Vision Pro)的开发者指南(3)-【3D UI SwiftUI和RealityKit】介绍

为了更深入地理解SwiftUI和RealityKit,建议你参加专注于SwiftUI场景类型的系列会议。这些会议将帮助你掌握如何在窗口、卷和空间中构建出色的用户界面。同时,了解Model 3D API将为你提供更多关于如何为应用添加深度和维度的知识。此外,通过学习RealityView渲染3D内容,你将能…

8.前端--CSS-显示模式

元素的显示模式 元素显示模式就是元素&#xff08;标签&#xff09;以什么方式进行显示&#xff0c;比如<div>自己占一行&#xff0c;比如一行可以放多个<span>。 1.块元素 常见的块元素 常见的块元素&#xff1a;<h1>~<h6>、<p>、<div>、…

01 Redis的特性

1.1 NoSQL NoSQL&#xff08;“non-relational”&#xff0c; “Not Only SQL”&#xff09;&#xff0c;泛指非关系型的数据库。 键值存储数据库 &#xff1a; 就像 Map 一样的 key-value 对。如Redis文档数据库 &#xff1a; NoSQL 与关系型数据的结合&#xff0c;最像关系…

大模型的学习路线图推荐—多维度深度分析【云驻共创】

&#x1f432;本文背景 近年来&#xff0c;随着深度学习技术的迅猛发展&#xff0c;大模型已经成为学术界和工业界的热门话题。大模型具有数亿到数十亿的参数&#xff0c;这使得它们在处理复杂任务时表现得更为出色&#xff0c;但同时也对计算资源和数据量提出了更高的要求。 …

二、arcgis 点shp数据处理

在工作中&#xff0c;很多时候客户会提供点坐标&#xff0c;那么要想把点坐标生成shp文件&#xff0c;有两种方法&#xff08;坐标系CGCS2000&#xff09;&#xff1a; 1.当只有个位数的点坐标时&#xff0c;可以直接在arcgisMap中添加&#xff0c;具体步骤如下&#xff1a; …

【JavaSE】第一个Java程序

前提引入 在JavaSE的系列中&#xff0c;将从第一个Java程序开始叙述&#xff0c;系统的把JavaSE的内容总结一次。毕竟这是第二次学习JavaSE的内容&#xff0c;因此感触也相对比较深一些。在JavaSE的初步计划中&#xff0c;大概有十一到十三篇文章&#xff0c;大致有&#xff1…

docker 安装手册

docker 安装手册 第一步卸载旧的docker (如果安装过Docker否则跳过此步) 以防万一最好执行一遍 yum -y remove docker docker-client docker-client-latest docker-common docker-latest docker-latest-logrotate docker-logrotate docker-engine 第二步&#xff0c;安装相关…

ROS第 11 课 参数的使用与编程方法

文章目录 第 11 课 参数的使用与编程方法1.服务模型2.rosparam参数2.1 rosparam详细参数2.2 运行海龟例程2.3 rosparam的使用 3.编程方法3.1 编写控制程序 4.运行程序 第 11 课 参数的使用与编程方法 1.服务模型 &emap;&emsp在ROS master当中有一个参数服务器&#x…

Linux系统Shell脚本 ----- 编程规范和变量详细解读(一)

一、程序编程风格 面向过程语言 开发的时候 需要 一步一步 执行 做一件事情&#xff0c;排出个步骤&#xff0c;第一步干什么&#xff0c;第二步干什么&#xff0c;如果出现情况A&#xff0c;做什么处理&#xff0c;如果出现了情况B&#xff0c;做什么处理 问题规模小&#…

imgaug库图像增强指南(35):【iaa.Fog】——轻松创建自然雾气场景

引言 在深度学习和计算机视觉的世界里&#xff0c;数据是模型训练的基石&#xff0c;其质量与数量直接影响着模型的性能。然而&#xff0c;获取大量高质量的标注数据往往需要耗费大量的时间和资源。正因如此&#xff0c;数据增强技术应运而生&#xff0c;成为了解决这一问题的…

gin如何实现热更新

什么是热更新&#xff1f; 一种不需要用户关闭应用或重新启动设备就能进行的软件更新技术。它可以快速地在线修复或升级应用程序的错误或功能&#xff0c;从而减少用户的等待时间并提高用户体验。 如何优雅停止服务&#xff1f; Go 1.8版本之后&#xff0c; http.Server 内置…

Unity中URP下的SimpleLit的 BlinnPhong高光反射计算

文章目录 前言一、回顾Blinn-Phong光照模型1、Blinn-Phong模型&#xff1a; 二、URP下的SimpleLit的 BlinnPhong1、输入参数2、程序体计算 前言 在上篇文章中&#xff0c;我们分析了 URP下的SimpleLit的 Lambert漫反射计算。 Unity中URP下的SimpleLit的 Lambert漫反射计算 我…

Unity - 简单音频

“Test_04” AudioTest public class AudioTest : MonoBehaviour {// 声明音频// AudioClippublic AudioClip music;public AudioClip se;// 声明播放器组件private AudioSource player;void Start(){// 获取播放器组件player GetComponent<AudioSource>();// 赋值…