最短路径算法(算法篇)
算法之最短路径算法
最短路径算法
概念:
-
考查最短路径问题,可能会输入一个赋权图(也就是边带有权的图),则一条路径的v1v2…vN的值就是对路径的边的权求和,这叫做赋权路径长,如果是无权路径长就是单纯的路径上的边数。
-
在赋权图,可能会出现负值边的情况,这样当我们去找最短路径时,可能会产生负值圈,毕竟一直走负值边可以将数值变得更短。
单源最短路径问题:
- 给定一个赋权图G=(V,E)和一个特定顶点s作为输入,找出从s到G中每一个其他顶点的最短赋权路径。
无权最短路径:
- 给定一个无权图G=(V,E)和一个起始顶点s作为输入,找出从s到G中每一个其他顶点的最短路径。
广度优先搜索算法(BFS)
概念:
- 广度优先搜索算法(BFS)用于在无权图或者边权相同的图中寻找最短路径。
- 该方法按层处理顶点,首先从起始点出发,进行发散找到与起始点邻接的顶点a,…,并将s到这些顶点的路径距离更新,然后将该点标记成已经访问的顶点并将该点的前一个顶点记录下来(被标记的顶点我们后面遇到就认为该点已经不需要再进行处理了),然后再从顶点a,…发散,找到该顶点的邻接顶点,然后重复操作,直到所有顶点都被标记完,就完成了搜索。
- 具体代码实现,是用一个队列,在迭代开始时,队列中只含有距离为迭代距离currdist的那些顶点,然后执行操作时,将距离currdist+1的顶点的那些顶点添加到队列中,只要当前距离为currdist顶点处理完,就会处理距离为currdist+1(也就是当前顶点发散的顶点)的顶点添加到队列中。
- 在队列中其实可以将know域也就是标记去掉,因为队列的形式已经说明执行过了,就不会在执行,因此相当于标记了。
代码:
//图的邻接表的结点信息
struct listnode{int data;bool flag; //判断是否访问过int path; //存储上一个顶点int dist; //距离listnode* next;
};//图的信息
class graph{
private:listnode *an; //邻接表形式存储图int vnum; //图中结点数
};//s为起点,an数组的邻接表表示图
void BFS(int s){queue<int>q;q.push(s);an[s].dist=0;while (!q.empty()){int v=q.front();q.pop();an[v].flag= true;listnode* p=an[v].next;while (p!= nullptr){if(an[p->data].dist==INT_MAX){an[p->data].dist=an[v].dist+1;an[p->data].path=v;q.push(p->data);}p=p->next;}}}
Dijkstra算法
概念:
- 用于求解赋权图的最短路径(无负值边),Dijkstra算法是解决单源最短路径问题的一般方法,并且该解法是贪心算法。Dijkstra只是BFS的升级版使他能够求赋权图的最短路径,如果求无权图Dijkstra跟BFS的做法一样!
- Dijkstra算法是分阶段的,该算法认为每一个阶段,都将该阶段当作最好的情况处理,类似于BFS算法,但是还是有不同的地方,比起BFS多出了需要进行每个阶段出现最好情况就进行更新路径。
- 具体做法是,从图中选取起始点v,然后找出邻接点,并将当前起始点到邻接点v3,v4…的距离更新,如果是赋权图就是dv+Cv,v3(就是顶点v到v3的权),如果是无权就是dv+1,并将v标记为已知。然后选取邻接点集中的一点再做为起始点,然后重复操作,将当前顶点的前一个顶点记录。当v到某个顶点的距离在当前阶段是最小的(最好情况),那么就进行更新,如果不是就无需更新。
- 具体来说,当我们扩展一个新结点时,我们会考虑它的所有未访问过的邻接结点,并计算从起始结点经过当前结点到达邻接结点的路径长度。如果这个长度小于已知的最短路径长度(或者邻接结点的路径长度尚未初始化),我们就更新邻接结点的路径长度。这样做的目的是通过不断更新路径长度来找到起始结点到所有其他结点的最短路径。
- 实现的时候可以使用优先队列来进行优化算法,只将顶点和其最短路径值进入队列中当队列非空,执行以下操作:u等于队顶的节点,w等于队顶节点的最短路径值;遍历u的所有边,如果能找到节点v最短路径值小于v的当前值,更新v,将v压入队列。结束
- 没有用优先队列优化的Dijkstra算法的时间复杂度为O(N²),如果使用优先队列,则时间复杂度为O(nlogn),可以不用考虑已知域;
Dijkstra跟BFS区别:
- 处理顶点:
- 在BFS算法中,当一个顶点被扩展时,它的所有未访问过的邻居顶点都被添加到队列中,这样它们将按照遍历的顺序逐个被访问。
- 在Dijkstra算法中,当一个顶点被扩展时,它的邻居顶点也被考虑,但是Dijkstra算法会计算扩展的顶点与其邻居之间的边的权重,并根据这个权重来更新到达邻居顶点的最短路径长度。这个更新过程使得Dijkstra算法能够处理带有非负权重的图。
- 选择下一个顶点:
- 在BFS算法中,下一个要被扩展的顶点是队列中的下一个顶点,也就是按照队列的先进先出(FIFO)原则选择。
- 在Dijkstra算法中,下一个要被扩展的顶点是距离起始点路径长度最小的顶点,也就是根据已知的最短路径长度来选择。这需要使用优先队列或者最小堆来高效地选择路径长度最小的顶点。
代码:
//图的邻接表的结点信息
struct listnode{int data;int path; //存储上一个顶点int dist; //最短距离int weight; //数组索引顶点跟该顶点的边的权重listnode* next;
};//图的信息
class graph{
private:listnode *an; //邻接表形式存储图int vnum; //图中结点数
};//v是起始点
void Dijkstra(int v){an[v].dist=0;queue<int>q;q.push(v);while (!q.empty()){int w=q.front();q.pop();listnode* p=an[w].next;while (p!= nullptr){if(an[w].dist+p->weight<an[p->data].dist){an[p->data].dist=an[w].dist+p->weight;an[p->data].path=w;q.push(p->data);}p=p->next;}}}
题目模板:
有向边单源最短路径问题
#include <bits/stdc++.h>
using namespace std;const int INF=0x3f3f3f3f;const int N=10;
int n;struct edge {int v, w;
};bool vis[N+1];int dijkstra(int start, const vector<vector<edge>>& graph) {int minroad[n+1];memset(minroad,INF,sizeof minroad);minroad[start] = 0;priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;pq.push({0, start});while (!pq.empty()) {auto [d, u] = pq.top();pq.pop();if(vis[u]) continue;vis[u]=true;for (const auto& edges : graph[u]) {int v = edges.v;int w = edges.w;if (minroad[u] + w < minroad[v]) {minroad[v] = minroad[u] + w;pq.push({minroad[v], v});}}}return minroad[n]!=INF?minroad[n]:-1;
}int main() {int m, start;cin >> n >> m >> start;vector<vector<edge>> graph(n + 1);for (int i = 0; i < m; i++) {int u, v, w;cin >> u >> v >> w;graph[u].push_back({v, w});}cout<<dijkstra(start, graph)<<endl;system("pause");return 0;
}
Floyd算法
概念:
- Floyd(弗洛伊德)算法是基于动态规划思想的算法,也称插点法,是全源最短路算法(全源就代表经过一次Floyd算法,每个点到各个点的最短路径都能算出来)
- 用于求任意一对顶点间的最短路径,此时图中的边的权值可以出现负数,但不能出现负环
- 时间复杂度为
O(n³)
,n为点个数
基本思想:
- 对于从i到j的弧,进行n次试探
- 首先考虑i,0,j是否存在,如果存在,则比较i,j和i,0,j的路径长度,去最短者进行更新i,j的最短路径
- 然后再添加顶点1,依次类推。
具体过程:
- 当一个图里有n个城市,求全源最短路径问题
- 定义城市k为从当前图拿出来,并重新插入图中的城市,
城市i
,城市j
分别为当前源城市
和目的城市
。dist[i\][j]表示城市i到城市j的最短路径
- 假设当前图中没有城市k,我们将城市k重新插入到图中
- 我们需要判断城市i到城市j的最短路径是否要更新,则比较路径经过城市k和原来的路径长度进行比较,如果经过城市k的路径长度更短,则更新dist[i][j],因此就为
dist[i][j]=min(dist[i][k]+dist[k][j],dist[i][j])
- 因此对这个图执行n次上述操作(也就是插点法),得出的dist二维数组就为全源的最短路径。
代码模板:
//dist[n][n]用来记录图中各点到各点的最短路径
void Floyd(int **dist){for(int k=0;k<n;++k){for(int i=0;i<n;++i){for(int j=0;j<n;++j){if(dist[i][k]+dist[k][j]<dist[i][j]){dist[i][j]=dist[i][k]+dist[k][j];}}}}
}
例题部分代码:
具体可看力扣1334. 阈值距离内邻居最少的城市,只包含求解全源最短路径代码
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;void Floyd(int n, vector<vector<int>>& edges){const int INF=0x3f3f3f3f;int dist[n][n];memset(dist,INF, sizeof(dist));for(int i=0;i<n;++i){dist[i][i]=0;}for(auto edge:edges){dist[edge[0]][edge[1]]=edge[2];dist[edge[1]][edge[0]]=edge[2];}//Floyd算法计算全源最短路代码for(int k=0;k<n;++k){for(int i=0;i<n;++i){for(int j=0;j<n;++j){if(dist[i][k]+dist[k][j]<dist[i][j]){dist[i][j]=dist[i][k]+dist[k][j];}}}}for(int i=0;i<n;++i){cout<<"第"<<i<<"城市到其他城市最短路径:";for(int j=0;j<n;++j)cout<<"("<<i<<","<<j<<","<<dist[i][j]<<")"<<" ";cout<<endl;}
}int main() {vector<vector<int>>edges{{0,1,2},{0,4,8},{1,2,3},{1,4,2},{2,3,1},{3,4,1}};Floyd(5,edges);system("pause");return 0;
}
尾言
完整版笔记也就是数据结构与算法专栏完整版可到我的博客进行查看,或者在github库中自取(包含源代码)
- 博客1: codebooks.xyz
- 博客2:moonfordream.github.io
- github项目地址:Data-Structure-and-Algorithms
相关文章:
最短路径算法(算法篇)
算法之最短路径算法 最短路径算法 概念: 考查最短路径问题,可能会输入一个赋权图(也就是边带有权的图),则一条路径的v1v2…vN的值就是对路径的边的权求和,这叫做赋权路径长,如果是无权路径长就是单纯的路径上的边数。…...
昇思25天学习打卡营第11天 | LLM原理和实践:基于MindSpore实现BERT对话情绪识别
1. 基于MindSpore实现BERT对话情绪识别 1.1 环境配置 # 实验环境已经预装了mindspore2.2.14,如需更换mindspore版本,可更改下面mindspore的版本号 !pip uninstall mindspore -y !pip install -i https://pypi.mirrors.ustc.edu.cn/simple mindspore2.2…...
反向散射技术(backscatter communication)
智能反射表面辅助的反向散射通信系统研究综述(知网) 1 反向散射通信技术优势和应用场景 反向散射通信技术通过被动射频技术发送信号,不需要一定配有主动射频单元,被认为是构建绿色节能、低成本、可灵活部署的未来物联网规模化应用关键技术之一,是实现“…...
致远CopyFile文件复制漏洞
复现版本 V8.0SP2 漏洞范围 V5&G6_V6.1至V8.0SP2全系列版本、V5&G6&N_V8.1至V8.1SP2全系列版本。 漏洞复现 上传文件 POST /seeyon/ajax.do?methodajaxAction&managerNameportalCssManager&rnd57507 HTTP/1.1 Accept: */* Content-Type: applicatio…...
MySQL 创建数据库
MySQL 创建数据库 在当今的数据驱动世界中,数据库是任何应用程序的核心组成部分。MySQL,作为一个流行的开源关系数据库管理系统,因其可靠性、易用性和强大的功能而广受欢迎。本文将详细介绍如何在MySQL中创建数据库,包括基础知识和最佳实践。 什么是MySQL数据库? MySQL…...
AbyssFish单连通周期边界多孔结构2D软件
软件介绍 AbyssFish单连通周期边界多孔结构2D软件(以下简称软件)可用于生成具备周期性边界条件的单连通域多孔结构PNG图片,软件可设置生成模型的尺寸、孔隙率、孔隙尺寸、孔喉尺寸等参数,并且具备孔隙形态控制功能。 软件生成的…...
Linux驱动开发-03字符设备驱动框架搭建
一、字符设备驱动开发步骤 驱动模块的加载和卸载(将驱动编译模块,insmod加载驱动运行)字符设备注册与注销(我们的驱动实际上是去操作底层的硬件,所以需要向系统注册一个设备,告诉Linux系统,我有…...
Zynq系列FPGA实现SDI视频编解码+图像缩放+多路视频拼接,基于GTX高速接口,提供8套工程源码和技术支持
目录 1、前言工程概述免责声明 2、相关方案推荐本博已有的 SDI 编解码方案本博已有的FPGA图像缩放方案本方案的无缩放应用本方案在Xilinx--Kintex系列FPGA上的应用 3、详细设计方案设计原理框图SDI 输入设备Gv8601a 均衡器GTX 解串与串化SMPTE SD/HD/3G SDI IP核BT1120转RGB自研…...
VS2019使用C#写窗体程序技巧(1)
1、打开串口 private void button1_Click(object sender, EventArgs e){myPort cmb1.Text;mybaud Convert.ToInt32(cmb2.Text, 10);databit 8;parity Parity.None;stopBit StopBits.One;textBox9.Text "2";try{sp new SerialPort(myPort, mybaud, parity, dat…...
Python爬虫-requests模块
前戏: 1.你是否在夜深人静的时候,想看一些会让你更睡不着的图片却苦于没有资源... 2.你是否在节假日出行高峰的时候,想快速抢购火车票成功..。 3.你是否在网上购物的时候,想快速且精准的定位到口碑质量最好的商品. …...
适用于PyTorch 2.0.0的Ubuntu 22.04上CUDA v11.8和cuDNN 8.7安装指南
将下面内容保存为install.bash,直接用bash执行一把梭解决 #!/bin/bash### steps #### # verify the system has a cuda-capable gpu # download and install the nvidia cuda toolkit and cudnn # setup environmental variables # verify the installation ######…...
使用conda安装openturns
目录 1. 有效方法2. 整体分析使用pip安装使用conda安装验证安装安装过程中可能遇到的问题 1. 有效方法 conda install -c conda-forge openturns2. 整体分析 OpenTURNS是一个用于概率和统计分析的软件库,主要用于不确定性量化。你可以通过以下步骤在Python环境中安…...
Chameleon:动态UI框架使用详解
文章目录 引言Chameleon框架原理核心概念工作流程 基础使用安装与配置创建基础界面 高级使用自定义组件响应式布局数据流与状态管理 结论 引言 Chameleon,作为一种动态UI框架,旨在通过灵活、高效的方式帮助开发者构建跨平台、响应用户交互的图形用户界面…...
7.10飞书一面面经
问题描述 Redis为什么快? 这个问题我遇到过,但是没有好好总结,导致答得很乱。 答:Redis基于内存操作: 传统的磁盘文件操作相比减少了IO,提高了操作的速度。 Redis高效的数据结构:Redis专门设计…...
[数据结构] 归并排序快速排序 及非递归实现
()标题:[数据结构] 归并排序&&快速排序 及非递归实现 水墨不写bug (图片来源于网络) 目录 (一)快速排序 类比递归谋划非递归 快速排序的非递归实现: (二)归并排序 归…...
面试题 12. 矩阵中的路径
矩阵中的路径 题目描述示例 题解 题目描述 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,返回 true ;否则,返回 false 。 单词必须按照字母顺序,通过相邻的单元格内的字母构成࿰…...
钉钉扫码登录第三方
钉钉文档 实现登录第三方网站 - 钉钉开放平台 (dingtalk.com) html页面 将html放在 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><title>登录</title>// jquery<script src"http://code.jqu…...
多GPU系统中的CUDA设备不可用问题
我们在使用多GPU系统时遇到了CUDA设备不可用的问题,详细情况如下: 问题描述: 我们在一台配备有8块NVIDIA GeForce RTX 3090显卡的服务器上运行CUDA程序时,遇到了如下错误: cudaErrorDevicesUnavailable: CUDA-capabl…...
python的列表推导式
文章目录 前言一、解释列表推导式二、在这句代码中的应用三、示例四、使用 for 循环的等价代码总结 前言 看看这一行代码:questions [q.strip() for q in examples["question"]] ,问题是最外层的 中括号是做什么的? 最外层的中括…...
类与对象(2)
我们在了解了类的简单创建后,需要对类的创建与销毁有进一步的了解,也就是对于类的构造函数与析构函数的了解。 目录 注意: 构造函数的特性: 析构函数: 注意: 该部分内容为重难点内容,在正常…...
迂回战术:“另类“全新安装 macOS 15 Sequoia beta2 的极简方法
概述 随着 WWDC 24 的胜利闭幕,Apple 平台上各种 beta 版的系统也都“跃跃欲出”,在 mac 上自然也不例外。 本次全新的 macOS 15 Sequoia(红杉)包含了诸多重磅升级,作为秃头开发者的我们怎么能不先睹为快呢࿱…...
如何设计一个秒杀系统,(高并发高可用分布式集群)
设计一个高并发、高可用的分布式秒杀系统是一个非常具有挑战性的任务,需要从架构、数据库、缓存、并发控制、降级限流等多个维度进行考虑。以下是一个典型的秒杀系统设计思路: 1. 系统架构 微服务架构 拆分服务:将系统功能拆分为多个微服务…...
深度优先搜索(所有可达路径)
参考题目:所有可达路径 题目描述 给定一个有 n 个节点的有向无环图,节点编号从 1 到 n。请编写一个函数,找出并返回所有从节点 1 到节点 n 的路径。每条路径应以节点编号的列表形式表示。 输入描述 第一行包含两个整数 N,M&…...
如何配置yolov10环境?
本文介绍如何快速搭建起yolov10环境,用于后续项目推理、模型训练。教程适用win、linux系统 yolo10是基于yolo8(ultralytics)的改进,环境配置跟yolo8几乎一模一样。 目录 第1章节:创建虚拟环境 第2章节:…...
『大模型笔记』GraphRAG:利用复杂信息进行发现的新方法!
GraphRAG:利用复杂信息进行发现的新方法! 文章目录 一. GraphRAG:利用复杂信息进行发现的新方法!1. 将RAG应用于私人数据集2. 整个数据集的推理3. 创建LLM生成的知识图谱4. 结果指标5. 下一步二. 参考文献微软官方推文:https://www.microsoft.com/en-us/research/blog/gra…...
数据结构1:C++实现变长数组
数组作为线性表的一种,具有内存连续这一特点,可以通过下标访问元素,并且下标访问的时间复杂的是O(1),在数组的末尾插入和删除元素的时间复杂度同样是O(1),我们使用C实现一个简单的边长数组。 数据结构定义 class Arr…...
C++入门基础篇(下)
目录 6.引用 6.1 引用的特性 6.2 const引用 7.指针和引用的关系 8.内联函数 9.nullptr 6.引用 引⽤不是新定义⼀个变量,⽽是给已存在变量取了⼀个别名,编译器不会为引⽤变量开辟内存空间, 它和它引⽤的变量共⽤同⼀块内存空间。比如&a…...
LabVIEW图像分段线性映射
介绍了如何使用LabVIEW对图像进行分段线性映射处理,通过对特定灰度值区间进行不同的线性映射调整,以优化图像的显示效果。案例中详细展示了如何配置和使用LabVIEW中的图像处理工具,包括设置分段区间、计算映射参数和应用映射函数等步骤。 实…...
Linux开发:进程件通过UDS传递内存文件句柄
Linux开发:进程间通过Unix Domain Socket传递文件描述符-CSDN博客 介绍了通过UDS传递文件描述符 Linux开发:通过memfd_create创建一个内存文件-CSDN博客 介绍了如果创建一个内存文件 将两者相结合,就可以通过UDS传递一块内存文件句柄也就是内存数据 //uds_fd.hpp #pragma …...
Internet Download Manager6.42最新下载器互联网冲浪小能手们!
今天我要来种草一个超级棒的宝贝——Internet Download Manager(简称 IDM)。这个小家伙简直是下载界的“速度与激情”代言人,让我彻底告别了等待的日子。🎉 IDM马丁正版下载如下: https://wm.makeding.com/iclk/?zoneid34275 …...
石家庄做网站备案有哪些公司/新闻发稿渠道
汉企奇点网络ZINI0908期班。(.NET)两位陈老师都很亲切呢 做程序猿预计前期会比较辛苦,但是有付出就会有收获,一分耕耘一分收获,要不断学习,持之以恒,以后学过的课要及时总结、记录、巩固。 程序…...
wordpress文章格式/百度搜索排名优化
慢慢将一些概念固化到基因内,才有可能和SPRING MVC,MEAN之类的好好作比较吧。 全都是基于1.8版本的教材,爽!!!...
建设网站项目简历/对网站提出的优化建议
--存储过程名和参数,参数中in表示传入参数,out标示传出参数,inout表示传入传出参数create procedure p_procedurecode(in sumdate varchar(10)) begindeclare v_sql varchar(500); --需要执行的SQL语句declare sym varchar(6);declare …...
两台电脑一台做服务器 网站/爱站网权重查询
虽然微软说asp.net能够匹配各种手机设备,但是手机型号众多,微软收集的手机资料有限,所以导致asp.net对很多手机匹配错误,本来可以支持html的却生成html,本来只支持wml的,缺生成了html导致手机无法浏览&…...
wordpress+最新版本/北京网站seo招聘
题目解决代码及点评 /************************************************************************/ /* 15. 有 N个国家名,要求按字母先后顺序排列(用起泡排序法)后输出*/ /***************************…...
网站里面的数据库是怎么做的/关键词出价计算公式
转载:https://blog.csdn.net/zhaoxiang66/article/details/81003094 1、先下载安装包 npm: npm install vuedraggable -S 2、引入插件,在你的vue文件的script标签里面这样引入 import draggable from vuedraggable 注册组件 components…...