最短路合集,Dijkstra,堆优化Dijkstra,BellmanFord,SPFA,Floyd,附完整代码及OJ链接

本文主要是介绍最短路合集,Dijkstra,堆优化Dijkstra,BellmanFord,SPFA,Floyd,附完整代码及OJ链接,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

    • 前言
    • 最短路径问题
    • 最短路径树
      • 单调性
      • 歧义性
      • 无环性
    • 单源最短路算法
      • Dijkstra算法
        • 最短路径子树序列
        • 贪心迭代
        • Dijkstra的实现
          • 朴素Dijkstra
          • 堆优化Dijkstra
      • BellmanFord算法
        • 算法原理
        • 算法实现
      • SPFA
        • 算法原理
        • 算法实现
    • 多源最短路
      • Floyd
        • 算法原理
        • 算法实现
    • OJ链接
    • 总结

前言

我们时常会面临着对路径选择的决策问题。例如在北京、上海、广州等城市,因其城市面积较大,乘地铁或公交都要考虑从A点到B点,如何换乘到达》现实中,每个人需求不同,选择方案就不尽相同。有人为了省钱,它需要的是路程最短(定价以路程长短为标准),另一些人省时间为了要赶飞机火车或者早晨上班不迟到,他最大的需求是总时间要短;还有一类人,如老人行动不便,或者上班族下班,忙碌一天累得要死,他们都不想多走路,哪怕车子绕远路耗时长也无所谓,关键是换乘要少,这样可以在车,上好好休息一下。这些都是老百姓的需求,简单的图形可以靠人的经验和感觉,但复杂的道路或地铁网就需要计算机通过算法计算来提供最佳的方案。本文就要来研究关于图的最短路径的问题。


最短路径问题

若以带权图来表示真实的通讯、交通、物流或社交网络,则各边的权重可能代表信道成本、交通运输费用或交往程度。此时我们经常关心的一类问题,可以概括为:

给定带权网络G = (V, E),以及源点(source) s ∈ V,对于所有的其它顶点v,s到v的最短通路有多长?该通路由哪些边构成?


最短路径树

单调性

如下图所示,设顶点s到v的最短路径为ρ。于是对于该路径上的任一顶点u,若其在最短路径ρ上对应的前缀为σ,则σ也必是s到u的最短路径之一(注意是之一)。否则,若从s到u还有另一严格更短的路径τ,则易见ρ不可能是s到v的最短路径。

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

歧义性

即便各边权重互异,从s到v的最短路径也未必唯一。另外,当存在非正权的边,并导致某个环路的总权值非正时,最短路径甚至无从定义。因此,为了避免歧义,后续叙述时我们都假定图G中各边权为正值

无环性

在下图所示的任意带权网络中,选取从源点到其余顶点的最短路径(若有多条,任选其一)。于是由以上单调性,这些路径的并集必然不含任何(有向)回路。这就意味着,它们应如图2和图3所示,构成所谓的最短路径树(shortest-path tree)

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

单源最短路算法

下面涉及到链式前向星存图,不熟悉的可以了解:一种实用的边的存储结构–链式前向星-CSDN博客

Dijkstra算法

Dijkstra ( 1930/05/11- 2002/08/06 ), 杰出的计算机科学家,1972年图灵奖得主

最短路径子树序列

将顶点ui到起点s的距离记作:dist[i] = dist(s, ui), 1 ≤ i ≤ n。不妨设di按非降序排列,即di ≤ dj 当且仅当 i ≤ j。于是与s自身相对应地必有:u1 = s

我们下图中给定一棵最短路径树T(u1,u2,u3……un),从T中删除(uk+1,uk+2……un)以及其关联的各边,得到的子图记作Tk,不难验证Tk一定是一棵树归纳证明Tk具有连通性即可,由于u1到un为按照到源点s也就是u1的距离非降序排序,我们从Tk + 1到Tk删除的uk+1一定是叶子节点,而根据最短路径的单调性可知uk+1作为Tk + 1中到源点最远的节点是没有子节点的。

故而子树序列{T1 , T2 ……Tn},构成了一个最短路径子树序列。

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

贪心迭代

我们颠倒上述过程,发现只要确定uk+1,就能从Tk扩展到Tk+1,故而,我们按照到s的距离进行非降序排序,逐一确定各个顶点{u1,u2,……,un},最终就能得到我们的最短路径树Tn。

现在的问题在于,如何高效的找到uk+1?

Dijkstra的实现

实际上,由最短路径子树序列的上述性质,每一个顶点uk+1都是在Tk之外,距离s最近者。故我们以Tk外各顶点距离s的距离为优先级,每次选取**uk+1(Tk之外,距离s最近者)**加入Tk并将其拓展至Tk+1后,需要且只需要更新那些仍在Tk+1之外,且与Tk+1关联的顶点的优先级数。

可见Dijkstra与我们的最小生成树算法prim算法仅有一处差异,即前者考虑uk+1到s的距离,后者考虑uk+1到Tk的距离。

朴素Dijkstra

算法流程

  • 到s距离数组dist,标记数组vis(用于记录是否已经进入Tk)

  • 初始化dist[s] = 0

  • 由于最短路径树只有n - 1条边,所以最多进行n - 1次迭代

  • 每轮迭代从Tk外的节点,即未标记的节点中选出dist[u]最小的u

  • 如果u不存在,说明已经得到最短路径树Tn,break

  • 否则,标记u,对u的邻点进行松弛更新

  • 算法结束,时间复杂度O(N^2)

    代码实现

void dijkstra(int s)
{vector<int> dist(n + 1, inf);//inf为无穷大的数dist[s] = 0;bitset<N> vis;for (int i = 1; i < n; i++){int mind = INT_MAX, u = 0;for (int j = 1; j <= n; j++)if (!vis[j] && dist[j] < mind)u = j, mind = dist[j];if (!u)break;vis[u] = 1;for (int j = head[u]; ~j; j = edges[j].nxt){int v = edges[j].v;if (vis[v])continue;if (dist[v] - edges[j].w > dist[u])dist[v] = dist[u] + edges[j].w;}}for (int i = 1; i <= n; i++)cout << dist[i] << " ";
}
堆优化Dijkstra

可见影响算法效率的大头就是uk + 1的选择,即然每次都选dist最小的节点,我们可以借助堆这一数据结构来快速选取,对Dijkstra进行优化。

  • 到s距离数组dist,标记数组vis(用于记录是否已经进入Tk)
  • 初始化dist[s] = 0,s进入优先级队列pq
  • 如果pq非空,取出pq堆顶的节点u
  • 如果pq已空,说明已经得到最短路径树Tn,break
  • 否则,标记u,对u的邻点进行松弛更新,对于被更新的点进入pq
  • 算法结束,时间复杂度O(NlogN)

代码实现

void dijkstra(int s)
{vector<int> dist(n + 1, inf);dist[s] = 0;bitset<N> vis;priority_queue<pii, vector<pii>, greater<pii>> pq;pq.emplace(0, s);while (pq.size()){auto [w, u] = pq.top();pq.pop();if (vis[u])continue;vis[u] = 1;for (int i = head[u]; ~i; i = edges[i].nxt){int v = edges[i].v;if (vis[v])continue;if (dist[v] - edges[i].w > dist[u])pq.emplace(dist[v] = dist[u] + edges[i].w, v);}}for (int i = 1; i <= n; i++)cout << dist[i] << " ";
}

前面我们叙述时,提到了我们假定图G中各边权为正值。这也是最短路径树无环性的关键,那么如果出现某个回路总权值为负值,我们是否仍能用Dijkstra算法求解呢?或者说,我们是否仍能得到最短路径树呢?外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

很可惜,不能。假如出现了一个负环,那么就会导致在这个环上每走一圈就会导致环内点的dist值减小,此时用Dijkstra求解是没有意义的。所以我们需要一种能够判断负环的最短路径算法,于是有了BellmanFord算法和SPFA算法。

BellmanFord算法

BellmanFord算法由动态规划创始人Richard Bellman和数学家Lester Ford创立。

算法原理

也提到了Richard Bellman是动态规划的创始人,所以BellmanFord算法利用了动态规划思想不过分吧(bushi

一提动态规划大家一定就不困了(bushi

那么dist[i]如何进行状态转移呢?
d i s t [ i ] = d i s t [ j ] + w ( j , i ) ,其中 < j , i > ∈ E , d i s t [ j ] + w ( i , j ) < d i s t [ i ] dist[i] = dist[j] + w(j,i),其中<j,i>\in E,dist[j] + w(i,j) \lt dist[i] dist[i]=dist[j]+w(j,i),其中<j,i>∈E,dist[j]+w(i,j)<dist[i]
由于最短路径树只有n - 1条边,所以我们进行n - 1轮迭代,每次迭代遍历所有边进行状态转移,在没有负环的情况下是可以正确求解的,如果第n轮仍能进行状态转移,那么说明存在负环。

算法实现

算法流程

  • 标记变量flag代表本轮迭代是否有状态更新
  • dist数组存储到源点距离
  • 进行n轮迭代,每轮迭代遍历所有边进行状态转移,flag初始为false
  • 如果发生状态转移,那么flag = true
  • 某次迭代后flag为false,说明dist已经是最终状态,return false,没有负环
  • 迭代结束后,return flag,此时flag的值代表是否有负环
  • 算法时间复杂度:(ne),n为节点数,e为边数
bool bellmanford(s)
{bool flag = false;memset(dist, inf, sizeof(dist));dist[s] = 0;for (int i = 0; i < n; i++){flag = false;for (int u = 1; u <= n; u++){if (dist[u] == inf)continue;for (int j = head[u]; ~j; j = edges[j].nxt){int v = edges[j].v;if (dist[v] > dist[u] + edges[j].w)dist[v] = dist[u] + edges[j].w, flag = true;}}if (!flag)return false;}return flag;
}

SPFA

段凡丁——SPFA的发明者。

SPFA已死

算法原理

SPFA是对BellmanFord的优化算法,即然BellmanFord是枚举所有边进行状态转移,但是并不是所有点都有资格进行状态转移的。不难分析出只有被本轮更新过的点下一轮才可能有资格对邻点进行更新,也就是说本轮你都没被更新,下一轮也轮不到你去更新别人,误人子弟(bushi。

即然对于每轮枚举的边有了限制,自然要引入辅助的数据结构了——队列,用于保存可能有资格更新邻接点的节点。

由于思想很简单,我们直接来看实现。

算法实现

算法流程

  • 辅助队列q,dist数组存距离,cnt[i]存源点s到i的路径长度,标记数组vis存储是否在队列内

  • 初始化s进队,dist[s] = cnt[s] = 0

  • 获取队首元素u,如果dist[u]为无穷大,则跳过

  • 否则遍历u的所有出边,邻接点v,如果dist[v] > dist[u] + edges[j].w,则更新dist[v],cnt[v]

    • 如果更新后cnt[v] >= n,说明有负环,返回true

    • 否则如果v不在对内,那么v入队,打标记

  • 队列空,返回false,无负环

  • 算法最坏时间复杂度仍为O(VE)

多提一嘴,出题人有很多方法可以卡死SPFA,如链式菊花图,随机网格图,网格套菊花……(有兴趣自行了解)

bool spfa(int s)
{bitset<N> vis;memset(dist, inf, sizeof(dist));memset(cnt, 0, sizeof(cnt));dist[s] = 0;queue<int> q;q.emplace(s);while (q.size()){auto u = q.front();q.pop();vis[u] = 0;if (dist[u] == inf)continue;for (int j = head[u]; ~j; j = edges[j].nxt){int v = edges[j].v;if (dist[v] > dist[u] + edges[j].w){dist[v] = dist[u] + edges[j].w, cnt[v] = cnt[u] + 1;if (cnt[v] >= n)return true;if (!vis[v])q.emplace(v), vis[v] = 1;}}}return false;
}

多源最短路

你已经学会单源最短路了,相信你一定有思路跑出多源最短路。

跑n次堆优化Dijkstra,你别说也不是不行(

Floyd

美国计算机科学家Robert·Floyd于1962年提出,该算法同样基于动态规划的思想

Floyd可以说是众多板子中最好写最无脑的,邻接矩阵建图,三层for……就这没了?

最喜欢的一集

算法原理

其实学BellmanFord的时候你可能就有一种感觉,为什么不直接用这样一个转移方程
d i s t [ i ] = m i n ( d i s t [ i ] , d i s t [ j ] + d i s t [ k ] ) ,其中 i , j 有路, j , k 有路 dist[i] = min(dist[i],dist[j]+dist[k]),其中i,j有路,j,k有路 dist[i]=min(dist[i],dist[j]+dist[k]),其中ij有路,jk有路
因为我们前面存图用的都是链式前向星或者邻接表,直接找到像上面公式中的j,k是不方便的

所以求多源最短路需要用到邻接矩阵存图,自然也就要求了题目的数据量在1e3以内,不然炸了

算法原理也十分简单,一个简单的动态规划,枚举k作为中间节点,枚举i,j更新dist[i][j]即可

算法实现

算法流程

  • 邻接矩阵g,初始化g[i][i] = 0,即每个节点到自己距离为0,其他都是inf(无穷大)
  • 枚举k作为中间节点,枚举i,j
  • 如果g[i][j] - g[i][k] > g[j][k],那么更新g[i][j]
  • 算法结束
  • 时间复杂度:O(N^3)

复杂度不咋地,但是真的很好写啊orz

    cin >> n >> m;//顶点数目和节点数目for (int i = 0; i < m; i++){cin >> u >> v >> w;g[v][u] = g[u][v] = w;}for (int i = 1; i <= n; i++)g[i][i] = 0;for (int k = 1; k <= n; k++)for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)if (g[i][j] - g[i][k] > g[j][k])g[i][j] = g[i][k] + g[j][k];for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++)cout << g[i][j] << " ";cout << '\n';}

OJ链接

有一个SPFA会被卡哟

P4779 【模板】单源最短路径(标准版) - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

P3371 【模板】单源最短路径(弱化版) - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)


总结

对于正权图,我们一定可以得到一棵最短路径树,单调性和歧义性保证了最短路径数不唯一,而我们可以利用这两个性质求解出所有的最短路径(tip:动态规划)。单源最短路径,如果无负环无脑堆优化Dijkstra,其它两种看情况不会卡的话就用,卡的话一定有其他方法。多元最短路一般数据量小的时候直接打板子。

如果不总结,等于没总结

这篇关于最短路合集,Dijkstra,堆优化Dijkstra,BellmanFord,SPFA,Floyd,附完整代码及OJ链接的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/541178

相关文章

Vue3 的 shallowRef 和 shallowReactive:优化性能

大家对 Vue3 的 ref 和 reactive 都很熟悉,那么对 shallowRef 和 shallowReactive 是否了解呢? 在编程和数据结构中,“shallow”(浅层)通常指对数据结构的最外层进行操作,而不递归地处理其内部或嵌套的数据。这种处理方式关注的是数据结构的第一层属性或元素,而忽略更深层次的嵌套内容。 1. 浅层与深层的对比 1.1 浅层(Shallow) 定义

大模型研发全揭秘:客服工单数据标注的完整攻略

在人工智能(AI)领域,数据标注是模型训练过程中至关重要的一步。无论你是新手还是有经验的从业者,掌握数据标注的技术细节和常见问题的解决方案都能为你的AI项目增添不少价值。在电信运营商的客服系统中,工单数据是客户问题和解决方案的重要记录。通过对这些工单数据进行有效标注,不仅能够帮助提升客服自动化系统的智能化水平,还能优化客户服务流程,提高客户满意度。本文将详细介绍如何在电信运营商客服工单的背景下进行

HDFS—存储优化(纠删码)

纠删码原理 HDFS 默认情况下,一个文件有3个副本,这样提高了数据的可靠性,但也带来了2倍的冗余开销。 Hadoop3.x 引入了纠删码,采用计算的方式,可以节省约50%左右的存储空间。 此种方式节约了空间,但是会增加 cpu 的计算。 纠删码策略是给具体一个路径设置。所有往此路径下存储的文件,都会执行此策略。 默认只开启对 RS-6-3-1024k

使用opencv优化图片(画面变清晰)

文章目录 需求影响照片清晰度的因素 实现降噪测试代码 锐化空间锐化Unsharp Masking频率域锐化对比测试 对比度增强常用算法对比测试 需求 对图像进行优化,使其看起来更清晰,同时保持尺寸不变,通常涉及到图像处理技术如锐化、降噪、对比度增强等 影响照片清晰度的因素 影响照片清晰度的因素有很多,主要可以从以下几个方面来分析 1. 拍摄设备 相机传感器:相机传

【专题】2024飞行汽车技术全景报告合集PDF分享(附原数据表)

原文链接: https://tecdat.cn/?p=37628 6月16日,小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞,这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示,公司准备量产,并计划今年四季度开启预售小鹏汇天分体式飞行汽车,探索分体式飞行汽车城际通勤。阅读原文,获取专题报告合集全文,解锁文末271份飞行汽车相关行业研究报告。 据悉,业内人士对飞行汽车行业

活用c4d官方开发文档查询代码

当你问AI助手比如豆包,如何用python禁止掉xpresso标签时候,它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来

安卓链接正常显示,ios#符被转义%23导致链接访问404

原因分析: url中含有特殊字符 中文未编码 都有可能导致URL转换失败,所以需要对url编码处理  如下: guard let allowUrl = webUrl.addingPercentEncoding(withAllowedCharacters: .urlQueryAllowed) else {return} 后面发现当url中有#号时,会被误伤转义为%23,导致链接无法访问

poj 1511 Invitation Cards(spfa最短路)

题意是给你点与点之间的距离,求来回到点1的最短路中的边权和。 因为边很大,不能用原来的dijkstra什么的,所以用spfa来做。并且注意要用long long int 来存储。 稍微改了一下学长的模板。 stack stl 实现代码: #include<stdio.h>#include<stack>using namespace std;const int M

poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)

poj 3259: 题意:John的农场里n块地,m条路连接两块地,w个虫洞,虫洞是一条单向路,不但会把你传送到目的地,而且时间会倒退Ts。 任务是求你会不会在从某块地出发后又回来,看到了离开之前的自己。 判断树中是否存在负权回路就ok了。 bellman代码: #include<stdio.h>const int MaxN = 501;//农场数const int

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n