11.3 最短路问题

11.3 最短路问题

第九章我们介绍过无权和带权DAG上的最短路最长路问题。这里给图上加上环。


11.3.1 Dijkstra 算法

Dijkstra算法适用于边权为正的情况,它可用于计算正权图上的单源最短路(就是从单个源点出发,到所有节点的最短路),该算法同时适用于有向图和无向图:

//初始化所有的结点为未标记,设d[0]=0,其他d[i]=INF
//循环n次{
//	在所有未标号的结点,选出d值最小的结点x
//	给结点x标记,对从x除法的边(x,y),更新d[y]=min{d[y],d[x]+w(x,y)} 
//}
memset(v,0,sizeof(v));//初始化结点,v[i]=1表示结点被标记 
for (int i=0;i<n;i++) d[i]=(i==0?0:INF);
for (int i=0;i<n;i++){int x,mind=INF;//mind为最小的d值 
	for (int y=0;y<n;y++) if (!v[y]&&d[y]<=mind) mind=d[x=y]; v[x]=1;
	//这里为了方便起见,用w[x][y]=INF来表示边(x,y)不存在
	//因为此时d[y]=min{d[y],d[x]+w(x,y)}不会修改d[y]的值 
	for (int y=0;y<n;y++) d[y]=min(d[y],d[x]+w[x][y]);
} 

其实就是动态规划和贪心法的结合,但是这里的复杂度为O(n2),可以继续优化到O(mlogn)(m为边的数量,n为点的数量),比较适用于稀疏图的情况(m比较大的时候我们称之为稠密图)。

用邻接表来进行优化。在这种表示法中,每个结点i都有一个链表,里面保存着从i出发的所有边:首先给每条边编号,然后用first[u]保存节点u的第一条边的编号,next[e]表示编号为e的边的“下一条边”的编号(紫书一般不喜欢用指针,而是用数组来实现链表,树等数据结构)。

int n,m,first[maxn],u[maxm],v[maxm],w[maxm],next[maxm];
//first[i]表示结点i的第一条边的编号,next[e]表示编号为e的边的"下一条边"的编号 
//u[i]和v[i]表示编号为i的边的左右两结点的编号
for (int i=0;i<n;i++) first[i]=-1;//初始化表头
for (int e=0;e<m;e++){cin>>u[e]>>v[e]>>w[e];
	next[e]=first[u[e]]; first[u[e]]=e;	//插入链表
} 

这个插入的方法稍微有点怪hhhh,不是一次确定表头,然后每次在表尾插入新边,而是每次将需要插入的新边插入到表的头部(将表的原头部作为新边的下一条边),然后修改表头的编号。

(其实就是头插法啦hhhh)

看不懂也没关系······事实上,本书的作者好像不是很喜欢邻接表,所以后面还是用vector和优先队列来写的:

//关于边的结构体,from和to表示起点和终点,dist表示边权 
struct Edge{int from,to,dist;
	Edge(int u,int v,int d):from(u),to(v),dist(d){}
};//关于结点的结构体,d表示d值,u表示结点的编号 
struct HeapNode{int d,u;//构造按照d值递增的排序方式 
	bool operator < (const HeapNode& rhs) const{return d>rhs.d}
};//d[i]表示s到点i的距离,p[i]表示当前(最优)路径下,i结点在路径中的上一个结点 
struct Dijkstra{int n,m,d[maxn],p[maxn],v[maxn];//v[i]表示点i是否被标记 
	vector<Edge>edges; vector<int>G[maxn];//G[i]表示从i出发的所有边 
	void init(int n){this->n=n;//初始化清空所有的表 
		for (int i=0;i<n;i++) G[i].clear(); edges.clear();
	}//读入有向图的边列表 
	void AddEdge(int from,int to,int dist){
		edges.push_back(Edge(from,to,dist));
		m=edges.size(); G[from].push_back(m-1);//m表示边的编号		
	}//算法主体,Q队列中存放的是并未标记过,但d值不为INF的结点
	//因为只有d值不为INF才有比较的意义(可能为d值最小的结点)
	//每次while循环去掉d值最小的结点,然后添加新增的d值不为INF的结点
	//和前面几章提到的单调队列非常类似 
	void Dijkstra(int s){priority_queue<HeapNode> Q;//因为是优先队列,队首即是d值最小的元素 
		for (int i=0;i<n;i++) d[i]=INF; d[s]=0; memset(v,0,sizeof(v));
		Q.push((HeapNode){0,s});
		while (!Q.empty()){ HeapNode x=Q.top(); Q.pop();
			if (!v[x.u]) continue; v[x.u]=1;
			//通过vector数组存储的边列表来寻找从结点x.u出发的边
			//然后对d值和p存储的路径进行更新,由于d值通过比较进行修改,所以一定不等于INF
			//将修改后的结点放入到优先队列之中 
			for (int i=0;i<G[x.u].size();i++) if (d[edges[G[x.u][i]].to]>d[x.u]+edges[G[x.u][i]].dist){
				d[edges[G[x.u][i].to]=d[x.u]+edges[G[x.u][i]].dist;
				p[edges[G[x.u][i].to]=G[x.u][i];
				Q.push((HeapNode){d[edges[G[x.u][i]].to],edges[G[x.u][i]].to});
			}
		}	
	}
};
 

大家看看就好,我甚至怀疑到这里开始换作者了,鬼知道为什么突然开始封装(修改路径和结点那里我写的不是很明白,因为我自己推的也不是很清楚,大家如果真的需要做进一步理解还是自己写一遍为好)。

还有一点就是我没有用引用来简化代码,所以看起来会显得非常复杂。


11.3.2 Bellman-Ford算法

Bellman-Ford算法是应对存在负权(事实上我真的无法理解负权的概念)的情况。就先搁置在这里,等到有解答再说吧emmmm


11.3.3 Floyd算法

如果需要每两点之间的最短路,不必调用n次Dijkstra算法或者Bellman-Ford算法。有一个更简单的方法——Floyd-Warshall算法(眼熟么?眼熟就对了,离散数学关系矩阵的传递闭包那里就有这个算法):

//初始化d[i][i]=0,其他的d值皆为INF
//添加的if条件用来避免数据溢出或者INF的边真的成为最短路的一部分 
for (int k=0;k<n;k++) for (int i=0;i<n;i++) for (int j=0;j<n;j++) if (d[i][j]<INF&&d[k][j]<INF)
	d[i][j]=min(d[i][j],d[i][k]+d[k][j]);

这个证明非常简单(数学归纳法甚至都不需要,感觉很直观),大家动一动自己聪明的大脑就知道了。

事实上这个算法我们早在第六章topo那里的自组合就已经用到过了,不过当时只用考虑两点之间是否有通路(我过了一天还做到类似的题,还把k,i,j的顺序搞反了hhhhh)。


11.3.4 竞赛题目选讲

11-4 电话圈 (UVA 247)

如果两个人相互打电话(直接或间接),说明他们在同一个电话圈之内。输入n个人的m次电话,找出所有电话圈。

分析:n的数据不大,最大只有25,用Floyd算法求出传递闭包之后,输出每个连通分量的所有人即可。

11-5 噪音恐惧症 (UVA 10048)

输入一个C个点S条边的无向带权图,边权代表每条路径的噪音值。当你从某点去往另一个点时,总是希望路上经过的最大噪音值最小。输入一些询问,每次询问两个点,输出这两点之间最大噪音值最小的路径。

分析:依旧是Floyd算法,逻辑关系稍微有点复杂,用d[i][j]表示i和j两点之间最小的最大噪音值。那么状态转移方程如下:

d[i][j]=min{max(d[i][k],d[k][j])},看着有点绕,实际上还是很简单的。

还有一题,等Bellman-Ford算法搞完再看。

热门文章

暂无图片
编程学习 ·

exe4j详细使用教程(附下载安装链接)

一、exe4j介绍 ​ exe4j是一个帮助你集成Java应用程序到Windows操作环境的java可执行文件生成工具&#xff0c;无论这些应用是用于服务器&#xff0c;还是图形用户界面&#xff08;GUI&#xff09;或命令行的应用程序。如果你想在任务管理器中及Windows XP分组的用户友好任务栏…
暂无图片
编程学习 ·

AUTOSAR从入门到精通100讲(126)-浅谈车载充电系统通信方案

01 引言 本文深入研究车载充电系统策略,设计出一套基于电动汽车电池管理系统与车载充电机的CAN通信协议,可供电动汽车设计人员参考借鉴。 02 电动汽车充电系统通讯网络 电动汽车整车控制系统中采用的是CAN总线通信方式,由一个整车内部高速CAN网络、内部低速CAN网络和一个充电…
暂无图片
编程学习 ·

CMake(九):生成器表达式

当运行CMake时&#xff0c;开发人员倾向于认为它是一个简单的步骤&#xff0c;需要读取项目的CMakeLists.txt文件&#xff0c;并生成相关的特定于生成器的项目文件集(例如Visual Studio解决方案和项目文件&#xff0c;Xcode项目&#xff0c;Unix Makefiles或Ninja输入文件)。然…
暂无图片
编程学习 ·

47.第十章 网络协议和管理配置 -- 网络配置(八)

4.3.3 route 命令 路由表管理命令 路由表主要构成: Destination: 目标网络ID,表示可以到达的目标网络ID,0.0.0.0/0 表示所有未知网络,又称为默认路由,优先级最低Genmask:目标网络对应的netmaskIface: 到达对应网络,应该从当前主机哪个网卡发送出来Gateway: 到达非直连的网络,…
暂无图片
编程学习 ·

元宇宙技术基础

请看图&#xff1a; 1、通过AR、VR等交互技术提升游戏的沉浸感 回顾游戏的发展历程&#xff0c;沉浸感的提升一直是技术突破的主要方向。从《愤怒的小鸟》到CSGO,游戏建模方式从2D到3D的提升使游戏中的物体呈现立体感。玩家在游戏中可以只有切换视角&#xff0c;进而提升沉浸…
暂无图片
编程学习 ·

flink的伪分布式搭建

一 flink的伪分布式搭建 1.1 执行架构图 1.Flink程序需要提交给 Job Client2.Job Client将作业提交给 Job Manager3.Job Manager负责协调资源分配和作业执行。 资源分配完成后&#xff0c;任务将提交给相应的 Task Manage。4.Task Manager启动一个线程以开始执行。Task Manage…
暂无图片
编程学习 ·

十进制正整数与二进制字符串的转换(C++)

Function one&#xff1a; //十进制数字转成二进制字符串 string Binary(int x) {string s "";while(x){if(x % 2 0) s 0 s;else s 1 s;x / 2;}return s; } Function two&#xff1a; //二进制字符串变为十进制数字 int Decimal(string s) {int num 0, …
暂无图片
编程学习 ·

[含lw+源码等]微信小程序校园辩论管理平台+后台管理系统[包运行成功]Java毕业设计计算机毕设

项目功能简介: 《微信小程序校园辩论管理平台后台管理系统》该项目含有源码、论文等资料、配套开发软件、软件安装教程、项目发布教程等 本系统包含微信小程序做的辩论管理前台和Java做的后台管理系统&#xff1a; 微信小程序——辩论管理前台涉及技术&#xff1a;WXML 和 WXS…
暂无图片
编程学习 ·

树莓派驱动DHT11温湿度传感器

1&#xff0c;直接使用python库 代码如下 import RPi.GPIO as GPIO import dht11 import time import datetimeGPIO.setwarnings(True) GPIO.setmode(GPIO.BCM)instance dht11.DHT11(pin14)try:while True:result instance.read()if result.is_valid():print(ok)print(&quo…
暂无图片
编程学习 ·

ELK简介

ELK简介 ELK是三个开源软件的缩写&#xff0c;Elasticsearch、Logstash、Kibana。它们都是开源软件。不过现在还新增了一个 Beats&#xff0c;它是一个轻量级的日志收集处理工具(Agent)&#xff0c;Beats 占用资源少&#xff0c;适合于在各个服务器上搜集日志后传输给 Logstas…
暂无图片
编程学习 ·

Linux 基础

通常大数据框架都部署在 Linux 服务器上&#xff0c;所以需要具备一定的 Linux 知识。Linux 书籍当中比较著名的是 《鸟哥私房菜》系列&#xff0c;这个系列很全面也很经典。但如果你希望能够快速地入门&#xff0c;这里推荐《Linux 就该这么学》&#xff0c;其网站上有免费的电…
暂无图片
编程学习 ·

Windows2022 无线网卡装不上驱动

想来 Windows2022 和 windows10/11 的驱动应该差不多通用的&#xff0c;但是死活装不上呢&#xff1f; 搜一下&#xff0c;有人提到 “默认安装时‘无线LAN服务’是关闭的&#xff0c;如果需要开启&#xff0c;只需要在“添加角色和功能”中&#xff0c;选择开启“无线LAN服务…
暂无图片
编程学习 ·

【嵌入式面试宝典】版本控制工具Git常用命令总结

目录 创建仓库 查看信息 版本回退 版本检出 远程库 Git 创建仓库 git initgit add <file> 可反复多次使用&#xff0c;添加多个文件git commit -m <message> 查看信息 git status 仓库当前的状态git diff 差异对比git log 历史记录&#xff0c;提交日志--pret…
暂无图片
编程学习 ·

用Postman生成测试报告

newman newman是一款基于nodejs开发的可以运行postman脚本的工具&#xff0c;使用Newman&#xff0c;可以直接从命令运行和测试postman集合。 安装nodejs 下载地址&#xff1a;https://nodejs.org/en/download/ 选择自己系统相对应的版本内容进行下载&#xff0c;然后傻瓜式安…
暂无图片
编程学习 ·

Java面向对象之多态、向上转型和向下转型

文章目录前言一、多态二、引用类型之间的转换Ⅰ.向上转型Ⅱ.向下转型总结前言 今天继续Java面向对象的学习&#xff0c;学习面向对象的第三大特征&#xff1a;多态&#xff0c;了解多态的意义&#xff0c;以及两种引用类型之间的转换&#xff1a;向上转型、向下转型。  希望能…