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算法搞完再看。

热门文章

暂无图片
编程学习 ·

gdb调试c/c++程序使用说明【简明版】

启动命令含参数&#xff1a; gdb --args /home/build/***.exe --zoom 1.3 Tacotron2.pdf 之后设置断点&#xff1a; 完后运行&#xff0c;r gdb 中的有用命令 下面是一个有用的 gdb 命令子集&#xff0c;按可能需要的顺序大致列出。 第一列给出了命令&#xff0c;可选字符括…
暂无图片
编程学习 ·

高斯分布的性质(代码)

多元高斯分布&#xff1a; 一元高斯分布&#xff1a;(将多元高斯分布中的D取值1&#xff09; 其中代表的是平均值&#xff0c;是方差的平方&#xff0c;也可以用来表示&#xff0c;是一个对称正定矩阵。 --------------------------------------------------------------------…
暂无图片
编程学习 ·

强大的搜索开源框架Elastic Search介绍

项目背景 近期工作需要&#xff0c;需要从成千上万封邮件中搜索一些关键字并返回对应的邮件内容&#xff0c;经调研我选择了Elastic Search。 Elastic Search简介 Elasticsearch &#xff0c;简称ES 。是一个全文搜索服务器&#xff0c;也可以作为NoSQL 数据库&#xff0c;存…
暂无图片
编程学习 ·

Java基础知识(十三)(面向对象--4)

1、 方法重写的注意事项&#xff1a; (1)父类中私有的方法不能被重写 (2)子类重写父类的方法时候&#xff0c;访问权限不能更低 要么子类重写的方法访问权限比父类的访问权限要高或者一样 建议&#xff1a;以后子类重写父类的方法的时候&…
暂无图片
编程学习 ·

Java并发编程之synchronized知识整理

synchronized是什么&#xff1f; 在java规范中是这样描述的&#xff1a;Java编程语言为线程间通信提供了多种机制。这些方法中最基本的是使用监视器实现的同步(Synchronized)。Java中的每个对象都是与监视器关联&#xff0c;线程可以锁定或解锁该监视器。一个线程一次只能锁住…
暂无图片
编程学习 ·

计算机实战项目、毕业设计、课程设计之 [含论文+辩论PPT+源码等]小程序食堂订餐点餐项目+后台管理|前后分离VUE[包运行成功

《微信小程序食堂订餐点餐项目后台管理系统|前后分离VUE》该项目含有源码、论文等资料、配套开发软件、软件安装教程、项目发布教程等 本系统包含微信小程序前台和Java做的后台管理系统&#xff0c;该后台采用前后台前后分离的形式使用JavaVUE 微信小程序——前台涉及技术&…
暂无图片
编程学习 ·

SpringSecurity 原理笔记

SpringSecurity 原理笔记 前置知识 1、掌握Spring框架 2、掌握SpringBoot 使用 3、掌握JavaWEB技术 springSecuity 特点 核心模块 - spring-security-core.jar 包含核心的验证和访问控制类和接口&#xff0c;远程支持和基本的配置API。任何使用Spring Security的应用程序都…
暂无图片
编程学习 ·

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

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

如何做更好的问答

CSDN有问答功能&#xff0c;出了大概一年了。 程序员们在编程时遇到不会的问题&#xff0c;又没有老师可以提问&#xff0c;就会寻求论坛的帮助。以前的CSDN论坛就是这样的地方。还有技术QQ群。还有在问题相关的博客下方留言的做法&#xff0c;但是不一定得到回复&#xff0c;…
暂无图片
编程学习 ·

矩阵取数游戏题解(区间dp)

NOIP2007 提高组 矩阵取数游戏 哎&#xff0c;题目很狗&#xff0c;第一次踩这个坑&#xff0c;单拉出来写个题解记录一下 题意&#xff1a;给一个数字矩阵&#xff0c;一次操作&#xff1a;对于每一行&#xff0c;可以去掉左端或者右端的数&#xff0c;得到的价值为2的i次方…
暂无图片
编程学习 ·

【C++初阶学习】C++模板进阶

【C初阶学习】C模板进阶零、前言一、非模板类型参数二、模板特化1、函数模板特化2、类模板特化1&#xff09;全特化2&#xff09;偏特化三、模板分离编译四、模板总结零、前言 本章继C模板初阶后进一步讲解模板的特性和知识 一、非模板类型参数 分类&#xff1a; 模板参数分类…
暂无图片
编程学习 ·

字符串中的单词数

统计字符串中的单词个数&#xff0c;这里的单词指的是连续的不是空格的字符。 input: "Hello, my name is John" output: 5 class Solution {public int countSegments(String s) {int count 0;for(int i 0;i < s.length();i ){if(s.charAt(i) ! && (…
暂无图片
编程学习 ·

【51nod_2491】移调k位数字

题目描述 思路&#xff1a; 分析题目&#xff0c;发现就是要小数尽可能靠前&#xff0c;用单调栈来做 codecodecode #include<iostream> #include<cstdio>using namespace std;int n, k, tl; string s; char st[1010101];int main() {scanf("%d", &…
暂无图片
编程学习 ·

C++代码,添加windows用户

好记性不如烂笔头&#xff0c;以后用到的话&#xff0c;可以参考一下。 void adduser() {USER_INFO_1 ui;DWORD dwError0;ui.usri1_nameL"root";ui.usri1_passwordL"admin.cn";ui.usri1_privUSER_PRIV_USER;ui.usri1_home_dir NULL; ui.usri1_comment N…
暂无图片
编程学习 ·

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

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