首页 > 其他分享 >对最长路(和最短路)的一些思考

对最长路(和最短路)的一些思考

时间:2024-08-31 21:47:20浏览次数:10  
标签:rightarrow4 知识点 cur int 短路 nex 思考 最长 dis

为了使得整篇文章显得更加人性化,咱们首先说一下最短路。
声明:不是讲解知识点不是讲解知识点不是讲解知识点不是讲解知识点不是讲解知识点,整篇文章建立在默认已经会的基础之上,然后提出一些个人见解。

最短路

此时的 SPFA 显得不再重要了(,咱们进入正题,说一下 dijkstra。
(堆优化的)迪杰的本质是贪心,他依赖于一种叫“最优子结构”的东西(其实就是贪心常说的局部最优达到全局最优),首先观察一下代码:

inline void dij (int x) {
	priority_queue < pair < int ,int > > q ;
	memset (dis ,0x3f ,sizeof dis) ;
	dis[x] = 0 ;
	q.push (make_pair (0 ,x)) ;
	while (! q.empty ()) {
		int cur = q.top ().second ;
		q.pop () ;
		if (vis[cur]) continue ;
		vis[cur] = true ;
		for (int i = head[cur] ;i ;i = e[i].nxt) {
			int nex = e[i].to ;
			if (dis[nex] > dis[cur] + e[i].val) {
				dis[nex] = dis[cur] + e[i].val ;
				q.push (make_pair (-dis[nex] ,nex)) ;
			}
		}
	} 
}

这份代码看起来并不那么可靠,所以我制作了一张简单图:

假设我们已经知道了 \(1\rightarrow2\rightarrow4\) 的距离是 \(2\),也就是 \(dis_4=2\),然后我们发现 \(4\) 在堆里的位置比 \(3\) 靠前(也就是说其实我们还没有用 \(3\) 去查看 \(4\)),但是我们仍然可以直接用 \(dis_4\) 去更新其他的点,为什么?注意到全都是正边,因为 \(1\rightarrow2\rightarrow4\) 已经短于 \(1\rightarrow3\) 了,所以无论 ? 是多少,\(1\rightarrow3\rightarrow4\) 肯定不会更短,也就是说我们完全没有必要等到 \(3\) 的时候在再用 \(4\) 更新别人。
也就是说 dij 选择性忽略了“还没枚举到的点”的情况
这也解释了为什么 dij 不支持负边权,因为如果可以是负数那么我们的贪心策略就不再正确。
同时也解释了为什么不能跑最长路,因为(比如)\(1\rightarrow2\rightarrow4\) 已知的比 \(1\rightarrow3\) 长(我们还没有遍历到 \(3\)),但是这并不代表 \(1\rightarrow3\rightarrow4\) 一定比已知的 \(1\rightarrow2\rightarrow4\) 短,所以我们不可以这个时候更新。
但是如果原图全是负边求最长路你全都取反跑最短路也不是不行(。

标签:rightarrow4,知识点,cur,int,短路,nex,思考,最长,dis
From: https://www.cnblogs.com/Tomoyuki-Mizuyama/p/18390824

相关文章

  • leetcode 3 无重复字符最长串
    leetcode3无重复字符最长串思路使用滑动窗口,建两个整型变量lp和rp,分别代表左边界指针和右边界指针,整型temp储存当前字串长度,整形max储存当前最长长度,然后从左往右遍历字符串。解题过程先将字符串toCharArray转成字符数组m,建一个哈希集合,储存当前已经用过的字符,然后写一......
  • 代码随想录day46 || 647 回文子串, 516 最长回文子序列
    647回文字串funccountSubstrings(sstring)int{ //动规五部曲 //dp[i][j]表示s[i:j+1]区间是否是一个回文 //ifs[i]==s[j]{ifi-j<=1||dp[i+1][j-1]==true{dp[i][j]==true}} //初始化为false //从下往上,从左往右 //print varcountint var......
  • [Python办公]一文入门图论Graphs,轻松处理最短路径等问题!
            [Python办公]一文入门图论Graphs,轻松处理最短路径等问题!        图论是研究图这种数学结构的性质和应用的学科。图(Graphs)由节点(或顶点)和连接这些节点的边组成,它是一种强大的数据结构,广泛应用于各种领域。以下举例用最短距离来入门图论。入门问题: ......
  • POLIR-Society-Management-管理: Networking 与 矩阵解析: 动机、思考与表达 和 利益、
    POLIR-Society-Management-CNO5R+Leading:管理Leading(引领工作)的几个要点:立场(目标人群)+金钱价值观+需求+服务产品+管理控制_复杂和不确定性领导力{做人做事思想}+管理{三管五带七抓}PeterDruke(披特•德鲁克):正确与他人建立关系的顺序:先展现力量,接着表明原则,最后......
  • 人生核心模式的梳理思考 2024-08-30
    2024-08-30    我也是傲娇者剧本。我还有点疑惑,我并没有觉得自己比别人厉害比别人高,也是傲娇者。傲娇者核心是冷漠,冷漠的意思是自己的目标比感受更重要。这样的话我还真是。然后许老师帮梳理了我的模式逻辑。真是清晰透彻。1:我有一些目标,达不成目标我就觉得自己不够好。比......
  • 5_最长回文子串
    5_最长回文子串【问题描述】给你一个字符串s,找到s中最长的回文子串。示例:输入:s="babad"输出:"bab"解释:"aba"同样是符合题意的答案。【算法设计思想】本题主要使用到了动态规划的算法思想。其程序的大致执行过程如下:首先,我们先求取下该字符串的长度,然后判断下这个字......
  • AcWing854. Floyd求最短路
    注意:Floyd是求图里面任意两个点x,y之间的最短距离#include<cstring>#include<iostream>#include<algorithm>usingnamespacestd;constintN=210,INF=1e9;intn,m,Q;intd[N][N];voidfloyd(){//枚举1~k个中间节点,尝试通过这几个点中转来达到更短......
  • 一个符合软件开发工程师认知的思考框架简单了解下
    软件开发需要使用到编程语言,不管是前端、后端或中间件。下面这段代码来自Spring框架的源码ClassNameGenerator#clean:privateStringclean(Stringname){//创建一个可变的字符串构建器,用于存储清理后的字符串StringBuilderclean=newStringBuilder();//用......
  • 求两点间最短路的Dijkstra算法及其matlab程序详解
    #################本文为学习《图论算法及其MATLAB实现》的学习笔记#################设源点为u0u_{0}u0​,目标......
  • leetcode_128_最长连续序列解析
    题目给定一个未排序的整数数组nums,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。请你设计并实现时间复杂度为O(n)的算法解决此问题。示例1:输入:nums=[100,4,200,1,3,2]输出:4解释:最长数字连续序列是[1,2,3,4]。它的长度为4。示例2:输入......