初识最短路径

一.最短路径的介绍

最短路径是图论和网络分析中一个重要的概念，它指的是在一个图或网络中连接两个节点或顶点的路径中，具有最小权重总和的路径。这个权重可以表示为路径上边或弧的长度、耗费、时间等，具体取决于问题的背景和应用场景。

如果你有学过最小生成树，你会发现，二者是有部分相同点的，都是在找权重和的最小值。

但是最小生成树找的是沟通所有节点的最小权重，而最短路径是找的是一个节点到另一个节点的最小权重。

因为从一个节点到另一个节点往往有多种路径，路径的长短也不同，我们的目的就是为了找到一个最短的路径，来达到省时省力的目的。

比如我们从A节点到E节点，分别有三条路径。

上路径：2（A->B）+4（B->E）=6

中路径：10（A->E）

下路径：4（A->C）+2（C->D）+6（D->E）=12

那么我们怎么使用代码找出最短路径呢？

用于解决最短路径可以使用Dijkstra 算法、SPFA算法、Floyd 算法等。

下面我们对这几种算法来介绍一下。

二.算法介绍

这里先给出一个例题，使用下面介绍成所有算法解决。

例题

输入数据：

4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

1.Dijkstra 算法

Dijkstra 算法基于贪心策略，通过逐步找到从起点到所有其他节点的最短路径来工作。它适用于权重为非负的有向图和无向图。

算法的实现有以下几个步骤：

1.distances：距离数组，用于存储从起点到每个节点的最短距离估计值。初始时，将起点到自身的距离设置为0，其他节点的距离设置为无穷大。

2.visited：标记数组，用于标记节点是否已经被访问过。初始时，将所有节点标记为未访问。

3.previous：前驱数组，用于记录到达每个节点的最短路径中，当前节点的前一个节点是哪个。

4.从起点开始，将起点标记为当前节点，更新起点到相邻节点的距离，并将这些相邻节点加入候选集。

5.从候选集中选择距离最短的节点作为当前节点，并将其标记为已访问。

6.对于当前节点的每个相邻节点，如果经过当前节点到达该相邻节点的路径比起始点直接到达该节点的路径更短，则更新距离数组和前驱数组。

7.重复步骤3和步骤4，直到所有节点都被访问过或候选集为空。

8.最终得到起点到每个节点的最短路径长度和最短路径。

下面是实现例题的完整代码（含注释）：

#include<bits/stdc++.h>
#define M 500010
#define inf 1234567890
using namespace std;
struct edge{
	int u,v,w,next;
}e[M];
struct node{
	int w,now;
	bool operator<(const node &k)const
	{
		return w>k.w;//堆优化，小的元素放在堆顶，大根堆 
	}
};
int head[M],re=0,n,m,s,v[M],dis[M];
priority_queue<node>q;
void add(int u,int v,int w)//链式前向星存图 
{
	e[++re].u=u;
	e[re].v=v;
	e[re].w=w;
	e[re].next=head[u];
	head[u]=re;
}
void dijkstra()
{
	for(int i=1;i<=n;i++) dis[i]=inf;//将点设置为无穷大 
	dis[s]=0;//起点设置为0 
	node p;
	p.w=0,p.now=s;
	q.push(p);
	while(!q.empty()){
		node k=q.top();
		q.pop();
		int u=k.now;
		if(v[u]) continue;//如果遍历过，直接跳过循环 
		v[u]=1;
		for(int i=head[u];i;i=e[i].next){//下一个点 
			int v=e[i].v;
			if(dis[v]>dis[u]+e[i].w)//更新最小权重 
			{
				dis[v]=dis[u]+e[i].w;
				q.push((node){dis[v],v});
			}		
		}
	}
}
int main()
{
	cin>>n>>m>>s;
	for(int i=0;i<m;i++){
		int u,v,w;
		cin>>u>>v>>w;//建边 
		add(u,v,w);
	}
	dijkstra();
	for(int i=1;i<=n;i++){
		cout<<dis[i]<<" ";
	}
	return 0;
}

我们来看运行结果：

也是成功AC。

2.SPFA算法

SPFA算法是一种用于解决单源最短路径问题的算法，是 Bellman-Ford 算法的一种优化版本。它通过队列实现松弛操作，以减少不必要的松弛次数，从而提高了算法的效率。

算法实现步骤：
1.distances：距离数组，用于存储从起点到每个节点的最短距离估计值。初始时，将起点到自身的距离设置为0，其他节点的距离设置为无穷大。

2.queue：队列，用于存储待处理的节点。初始时，将起点加入队列。

3.in_queue：标记数组，用于标记节点是否已经在队列中。初始时，将起点标记为在队列中。

4.从队列中取出一个节点作为当前节点，遍历该节点的所有相邻节点。

5.对于每个相邻节点，如果经过当前节点到达该相邻节点的路径比起始点直接到达该节点的路径更短，则更新距离数组，并将该相邻节点加入队列。

6.重复直到队列为空。

下面是实现例题的完整代码：

#include<bits/stdc++.h>
#define M 500010
#define inf 1234567890
using namespace std;
struct edge{
	int u,v,w,next;
}e[M];
int head[M],re=0,n,m,s,v[M],dis[M];
void add(int u,int v,int w)//链式前向星存图 
{
	e[++re].u=u;
	e[re].v=v;
	e[re].w=w;
	e[re].next=head[u];
	head[u]=re;
}
queue<int>q;//队列优化 
void SPFA()
{
	for(int i=1;i<=n;i++) dis[i]=inf;//将点设置为无穷大 
	dis[s]=0;//起点设置为0 
	q.push(s);
	while(!q.empty()){//直到所有节点全部入队，不会再有新的节点入队，慢慢出队至停止循环 
	    int k=q.front();
		q.pop();
		v[k]=0;
		for(int i=head[k];i;i=e[i].next){//下一个点 
			int p=e[i].v;
			if(dis[p]>dis[k]+e[i].w)//更新最小权重 
			{
				dis[p]=dis[k]+e[i].w;
				if(!v[p])//如果不在队列里面，则入队 
				{
					v[p]=1;
					q.push(p);
				}
			}		
		}
	}
}
int main()
{
	cin>>n>>m>>s;
	for(int i=0;i<m;i++){
		int u,v,w;
		cin>>u>>v>>w;//建边 
		add(u,v,w);
	}
	SPFA();
	for(int i=1;i<=n;i++){
		cout<<dis[i]<<" ";
	}
	return 0;
}

下面是运行结果：

虽然运行结果正确，但是SPFA算法容易被卡数据，导致时间超限。

3.Floyd 算法

Floyd算法的时间复杂度为O(N^3)，其中N是节点的数量。因此，对于大型图，Floyd算法可能会变得相对缓慢。然而，与其他单源最短路径算法不同，Floyd算法可以同时计算任意两个节点之间的最短路径，这在某些情况下可能是更方便的。

Floyd算法的核心是下面这个方程式，来自动态规划。

dp[j][k]=min(dp[j][k],dp[j][i]+dp[i][k]);

算法实现步骤：

  1. 初始化距离矩阵：将矩阵D初始化为图的邻接矩阵，如果两个节点之间有直接的边，则距离为边的权重；否则，距离为无穷大。同时，将对角线上的元素（即节点到自身的距离）初始化为0。

  2. 三重循环：对于每一对节点（i，j）作为可能的中间节点k，检查是否存在路径从节点i到节点j通过节点k的路径比直接从i到j的路径更短。如果是，则更新路径长度。

  3. 返回最终的距离矩阵D，其中D[i][j]表示从节点i到节点j的最短路径长度。

Floyd算法是这三种算法中最简单的，核心代码只有一点。

for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==j||dp[j][i]==inf) continue;
			for(int k=1;k<=n;k++){
				dp[j][k]=min(dp[j][k],dp[j][i]+dp[i][k]);
			} 
		}
	}

下面是完整代码：

#include<bits/stdc++.h>
using namespace std;
#define M 10010
#define inf 1234567890
int n,m,s,dp[M][M];
void floyd()
{
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==j||dp[j][i]==inf) continue;//找存在边 
			for(int k=1;k<=n;k++){
				dp[j][k]=min(dp[j][k],dp[j][i]+dp[i][k]);//更新最小权重 
			} 
		}
	}
}
int main()
{
	cin>>n>>m>>s;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	dp[i][j]=inf;//初始化矩阵 
	
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		dp[u][v]=min(dp[u][v],w);//防止重边 
	}
	dp[s][s]=0;
	floyd();
	for(int i=1;i<=n;i++){
		cout<<dp[s][i]<<" ";
	}
	return 0;
}

下面是运行结果：

结果虽然正确，但是对于这题来说，运行速度太慢了。

所以在做题时，需要按照题目要求来选择合适算法。

三.总结

  1. Dijkstra算法：

    • 简介： Dijkstra算法是解决单源最短路径问题的一种贪心算法。它从起点开始，逐步找到从起点到所有其他节点的最短路径。
    • 运行速度： 在最坏情况下，Dijkstra算法的时间复杂度为O((V+E)logV)，其中V是节点数，E是边数。在使用最小堆的实现中，它通常具有较好的性能。

  2. SPFA算法：

    • 简介： SPFA算法是Bellman-Ford算法的一种优化版本，通过使用队列来避免不必要的重复松弛操作，提高了效率。
    • 运行速度： SPFA算法的平均时间复杂度通常被认为是O(kE)，其中k是一个常数。在实际应用中，它的性能通常比Bellman-Ford算法好，但对于存在负权回路的图，SPFA算法可能陷入死循环。

  3. Floyd算法：

    • 简介： Floyd算法是一种动态规划算法，用于解决图中所有节点对之间的最短路径问题。它通过迭代更新每一对节点之间的最短路径长度。
    • 运行速度： Floyd算法的时间复杂度为O(N^3)，其中N是节点的数量。在大型图上可能变得相对缓慢，但与其他单源最短路径算法不同，Floyd算法可以同时计算任意两个节点之间的最短路径。

速度比较：

  • Dijkstra算法通常在稠密图上表现良好，特别是当使用最小堆等数据结构进行优化时。
  • Floyd算法的运行速度可能在大型图上较慢，但由于同时计算所有节点对之间的最短路径，它在某些情况下可能更方便。

总体而言，选择算法通常取决于图的规模、稀密度、边权重分布以及是否需要同时计算所有节点对之间的最短路径。

本篇完~

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

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

相关文章

基于Spring Boot的古典舞在线交流平台设计与实现，计算机毕业设计(带源码+论文)

基于Spring Boot的古典舞在线交流平台设计与实现，计算机毕业设计(带源码+论文)

源码获取地址&#xff1a; 码呢-一个专注于技术分享的博客平台一个专注于技术分享的博客平台,大家以共同学习,乐于分享,拥抱开源的价值观进行学习交流http://www.xmbiao.cn/resource-details/1758349555560165377
阅读更多...
Compose 自定义 - 数据转UI的三阶段（组合、布局、绘制）

Compose 自定义 - 数据转UI的三阶段（组合、布局、绘制）

一、概念 Compose 通过三个阶段把数据转化为UI&#xff1a;组合&#xff08;要显示什么&#xff09;、布局&#xff08;要显示在哪里&#xff09;、绘制&#xff08;如何渲染&#xff09;。 组合阶段 Compisition 界面首次渲染时会将可组合函数转化为一个个布局节点 Layout Nod…
阅读更多...
NVIDIA Chat with RTX

NVIDIA Chat with RTX

NVIDIA在2月13日发布了Chat With RTX&#xff0c;这是一款类似于ChatGPT的免费个性化 AI 聊天机器人&#xff0c;可以在配备 Nvidia RTX 显卡的 PC 上本地运行。它使用Mistral或Llama开放权重LLM&#xff0c;可以搜索本地文件并回答有关它们的问题。本文中我们一起来了解一下Ch…
阅读更多...
【网络安全】什么样的人适合学？该怎么学？

【网络安全】什么样的人适合学？该怎么学？

有很多想要转行网络安全或者选择网络安全专业的人在进行决定之前一定会有的问题&#xff1a; 什么样的人适合学习网络安全&#xff1f;我适不适合学习网络安全&#xff1f; 当然&#xff0c;产生这样的疑惑并不奇怪&#xff0c;毕竟网络安全这个专业在2017年才调整为国家一级…
阅读更多...
Arduino ESP8266/ESP32 TCP/UDP通讯例程

Arduino ESP8266/ESP32 TCP/UDP通讯例程

Arduino ESP8266/ESP32 TCP/UDP通讯例程 &#x1f527;需要配合上位机软件&#xff1a;网络调试助手&#xff08;http://www.cmsoft.cn/software.html&#xff09; &#x1f4dd;ESP8266/ESP32 作为TCP客户端使用 //要将ESP8266/32 Arduino TCPClient的调试输出发送到串口&am…
阅读更多...
OpenAI首个文生视频模型亮相，你觉得咋样？

OpenAI首个文生视频模型亮相，你觉得咋样？

2月16日凌晨&#xff0c;OpenAI再次扔出一枚深水炸弹&#xff0c;发布了首个文生视频模型Sora。据介绍&#xff0c;Sora可以直接输出长达60秒的视频&#xff0c;并且包含高度细致的背景、复杂的多角度镜头&#xff0c;以及富有情感的多个角色。 目前官网上已经更新了48个视频d…
阅读更多...
在Visual Studio中搭建Dynamo Python开发环境，效率飞一般的增长

在Visual Studio中搭建Dynamo Python开发环境，效率飞一般的增长

最近在学习Dynamo中Python Script的用法&#xff0c;发现这个东西用起来太不友好了&#xff0c;不支持自动缩进&#xff0c;不支持自动填充和提示。用过Visual Studio做二开的都知道&#xff0c;在引用了Revit api以后&#xff0c;就可以自动填充和提示了。 本来英语就不好&am…
阅读更多...
UI风格汇：毛玻璃风格风靡的原因解读

UI风格汇：毛玻璃风格风靡的原因解读

Hello&#xff0c;我是大千UI工场&#xff0c;设计风格是我们新开辟的栏目&#xff0c;主要讲解各类UI风格特征、辨识方法、应用场景、运用方法等&#xff0c;本次带来的是毛玻璃风格的解读&#xff0c;有设计需求可以私聊。 一、什么是毛玻璃风格 毛玻璃风格&#xff08;Fros…
阅读更多...
Mysql5.6忘记密码，如何找回（windows）

Mysql5.6忘记密码，如何找回（windows）

mysql5.6安装 第一步&#xff1a;关闭正在运行的数据库服务 net stop mysql第二步&#xff1a;在my.ini文件当中的[mysqld] 任意一个位置放入 skip-grant-tables第三步&#xff1a;启动mysql服务 net start mysql第四步&#xff1a;服务启动成功后就可以登录了&#xff0c;…
阅读更多...
Typora＋PicGO＋腾讯云COS做图床教程

Typora＋PicGO＋腾讯云COS做图床教程

文章目录 Typora&#xff0b;PicGO&#xff0b;腾讯云COS做图床教程一、为什么使用图床二、Typora、PicGO和腾讯云COS介绍三、下载Typora和PicGOTyporaPicGO 四、配置Typora、PicGO和腾讯云COS腾讯云COS配置PicGO配置Typora配置 Typora&#xff0b;PicGO&#xff0b;腾讯云COS做…
阅读更多...
AI Infra论文阅读之LIGHTSEQ（LLM长文本训练的Infra工作）

AI Infra论文阅读之LIGHTSEQ（LLM长文本训练的Infra工作）

感觉这篇paper有几个亮点&#xff0c;首先把Megatron-LM的Self-Attention模块的模型并行方式变成序列并行&#xff0c;优化了通信量&#xff0c;同时通过计算和通信重叠近一步压缩了训练迭代时间。另外&#xff0c;在使用重计算的时候发现当前Huggingface/Megatron-LM的重计算策…
阅读更多...
电容充电速度

电容充电速度

对电容充电的过程中&#xff0c;电容器充电的电压为&#xff0c;求电容器的充电速度。
阅读更多...
【Algorithms 4】算法（第4版）学习笔记 08 - 3.1 符号表

【Algorithms 4】算法（第4版）学习笔记 08 - 3.1 符号表

文章目录 前言参考目录学习笔记1&#xff1a;API1.1&#xff1a;遵循的规则1.2&#xff1a;ST 用例举例1.2.1&#xff1a;行为测试用例1.2.2&#xff1a;性能测试用例2&#xff1a;基本实现2.1&#xff1a;无序链表处理2.2&#xff1a;初级ST实现小结2.3&#xff1a;有序数组的…
阅读更多...
2.14：二维数组、非函数实现strcat、strcmp、strcpy、strlen

2.14：二维数组、非函数实现strcat、strcmp、strcpy、strlen

1.编程实现二维数组的杨辉三角 程序代码&#xff1a; 1 #include<stdio.h>2 #include<string.h>3 #include<stdlib.h>4 int main(int argc, const char *argv[])5 {6 int n;7 printf("please enter n:");8 scanf("%d",&…
阅读更多...
Python四级考试笔记

Python四级考试笔记

Python四级考试笔记【源源老师】 四级标准 一、 理解函数及过程、函数的参数、函数的返回值、变量作用域等概念。 二、 能够创建简单的自定义函数。 三、 理解算法以及算法性能、效率的概念&#xff0c;初步认识算法优化 效率的方法。 四、 理解基本算法中递归的概念。 五、 掌…
阅读更多...
如何解决缓存和数据库的数据不一致问题

如何解决缓存和数据库的数据不一致问题

数据不一致问题是操作数据库和操作缓存值的过程中&#xff0c;其中一个操作失败的情况。实际上&#xff0c;即使这两个操作第一次执行时都没有失败&#xff0c;当有大量并发请求时&#xff0c;应用还是有可能读到不一致的数据。 如何更新缓存 更新缓存的步骤就两步&#xff0…
阅读更多...
Linux下解压tar.xz文件的命令

Linux下解压tar.xz文件的命令

tar -c: 建立压缩档案-x&#xff1a;解压-t&#xff1a;查看内容-r&#xff1a;向压缩归档文件末尾追加文件-u&#xff1a;更新原压缩包中的文件 ------------------------------------------ 这五个是独立的命令&#xff0c;压缩解压都要用到其中一个&#xff0c;可以和别的…
阅读更多...
谷歌学术引用无法显示，提示“偶尔出现错误，请F5刷新！”

谷歌学术引用无法显示，提示“偶尔出现错误，请F5刷新！”

如图&#xff0c;我想进行EndNote引用&#xff0c;总是出现提示“偶尔出现错误&#xff0c;请F5刷新&#xff01;” 就是一直在出现&#xff0c;根本无法下载引用的内容。 最后发现了原因&#xff1a;我是使用谷歌学术镜像进行搜索的&#xff0c;并不是在https://scholar.goog…
阅读更多...
Mybatis速成（一）

Mybatis速成（一）

文章目录 Mybatis速成&#xff08;一&#xff09;前言1. 快速入门1.1 入门程序分析1.2 入门程序实现1.2.1 准备工作1.2.1.1 创建springboot工程1.2.1.2 数据准备 1.2.2 配置Mybatis1.2.3 编写SQL语句1.2.4 单元测试 1.3 解决SQL警告与提示 2. JDBC介绍(了解)2.1 介绍2.2 代码2.…
阅读更多...
anomalib1.0学习纪实-续1：增加新算法

anomalib1.0学习纪实-续1：增加新算法

0、基本信息 现在我要增加一个新算法&#xff1a;DDAD 他的代码&#xff0c;可以在github中找到&#xff1a;GitHub - arimousa/DDAD 一、基础操作&#xff1a; 1、修改anomalib\src\anomalib\models\__init__.py 我增加的第33行和61行&#xff0c; 2、 增加ddad文件夹和文…
阅读更多...
最新文章

Copyright @ 2022~2023