细节问题做解释相关题型应用非常值得哟尤其是刚入门的小白学习干货满满通俗易懂欢迎大家点赞收藏阅读呀

制作日期2025.01.27

5.1为什么我们从dist中选的的最小的点dist值一定是最小源点距

5.2为什么选择最小源点距的点u去更新v再次放入v对应的dist值不一定是最小的

5.3为什么每次不是在更新dist操作的时候标记1对v而是选出最小源点距的点u后给u标记1

6.1基本原理

提出的一种用于解决图中单个源点到其他各节点最短路径问题的经典算法。

该算法适用于带权有向图或无向图且图中边的权重必须是非负的。

其目的是找到从源节点到图中所有其他节点的最短路径通过逐步确定最短路径长度的节点集合不断更新源节点到其他节点的最短距离估计最终实现找到最短路径的目标。

我们先明确一下它可以处理有无向图但是就是不能处理负权边后面我们会解释。

1.2形象举例演示

distflagpre记录i点到源点的距离当前认为最小的后续可能更新标记已经完成最小源点距的点记录当前点的前驱节点方便找路径.........

其实还会有个二维path表方便我们

拿到两点及两点边之间的权其次就是这里我们默认编号从1开始但是数组下标确实0我们就从1开始放入。

其实它可以从任意点开始来找到任意点的了路径那么下面我们就从1号开始

初始化操作

每次从dsit数组中选没找到最小distflag数组对应位置标记位0然后它就是最短源点距给它的flag标记成1开始从它作为下一个点的前驱去找到下一个点的距离如果此时源点可借助这个点到达下一个点比之前距离小就跟新对应dist然后记录前驱也就是当前这个被选中的点依次循环知道dist数组对应下标位置都被标记1即再也找不到就完成查找工作了

下面动态效果展示一下

相信到这里大家应该明白了是如何操作的了那么下面我们着重的就是算法实现了

标准版

初始化为正无穷大表示源点到这些节点的最短路径尚未确定。

维护一个集合

1.3.2核心步骤

首先需要两个循环第一个循环确定已经完成查找到最短源点距的点u一定要标记好防止再次查找到它然后通过u开始拓展找可到达的边看看能否借助u到达v的源点距小于之前dist数组中填写的值如果小就更换并且记录前驱节点依次重复此步骤直到无法找出中间点即可。

注那么问题来了这里难点不是怎么操作而是怎么判断是否合法也就是两种选点时候的判断博主给大家总结好了以及相关分析

①选中间点u

1·这里我们只需要判断它是否被找到了最短源点距根据flag数组标记

2·以及它能不能被源点到达即可第一次肯定是选的我们标记的0但是之后如果选出了我们设置的无穷这个点不能被源点直达也不可以借助其他中间点到达也就是它是不能选的直接就是完成工作了break掉

2·其次就是源点可以借助u到达v即u到v有路线这里我们可以省因为后面判断两个路线最短时候包含了这点

3·最重要的就是路线比较了即借助中间点u的路线和原来填写的路线要最短的进行更新dist数组

注这里我们也许会问这个还要不要判断源点是否可达v也就是dist[V]不能为无穷

肯定是不需要否则第一次以源点作为前驱中间点选择的时候不就完蛋咯。

1.4伪代码模版

dist_min();//完成中间点选择不合适直接退出完成工作

break;

//u一定是源点可达的点标记已经找到的最短路的点;//作为中间点一定dist里最短路径无需更新u了for

{if

上面的要点我们都讲完了代码不成问题了下面展示下博主自己实现的代码以及一些细节处理的解释操作超详细版

2.1代码展示

IMAX;//注意如果dist数组中可选的中间点只有dist为IMAX也就是源点不可达的点这里必须返回提示一下也就是找不到idfor

(int

{//符合条件uv可达间接隐含v不是最短源点距符合两路取短if

(path[u][v]

无向图}init_pre();Dijkstra(3);find_min();cout

endl;getpath(1);//等于自身可能自身成环也可能无法到达return

2.2测试效果

我们就以上面模拟的为例子源点选择1号并查看一下到2号的最短路径

2.3时间复杂度分析

当然了这里我们不难发现时间复杂度由于套了两层循环到了ON^2级别那么可不可以优化呢。

但是是可以的我们可以借助优先队列给它优化一下,这样当数据范围特别大的时候我们就不用通过手动循环去查找了而是可以直接利用stl容器特性解决。

我们已经看到了如果数据大上面的朴素法还是不行的因此下面就借助优先队列完成

首先我们变化的大致可以理解为只是优化了查找中间点u工作以及放入u的临边点v点的操作。

这里剧透一下因为我们这操作相当于黑盒因此我们只管直接拿直接放优先队列是混乱的我们只需要它自己帮我们完成我们想要的操作即可。

3.1优化后代码深度剖析讲解

v[N];//表示i为始点v[i]里面的的每个pair的元素代表它的下一个点以及到达的边权

pairint,

//其次就是注意外层pair顺序我们是优先以路径长短作为判断的ll和int不能颠倒与定义的vector的pair类型不同

③剖析解释一下这个优先队列

这里的优队就是为了把遍历朴素法的dist数组的复杂直接转成靠stl容器完成选择出这个已经找到最短路径的中间点然后开始搜索继续放入队列)。

这里为了我们不仅可以知道源点到某点的最短距离以及路径故我们每次都把前驱节点推进去

注队列中的元素不完全是某点最短路径长度是所有能到达此点的路径依靠stlpq的性质完成自己筛选出最短

④这两个容器变量类型不能混杂

注意外层pair顺序我们是优先以路径长短作为判断的ll和int不能颠倒与定义的vector的pair类型不同

1·选择中间点u首先我们把源点推进去启动优先队列的操作接着就是确认源点已经是最短源点距给它标记防止下一次还选到它注符合中间点筛选条件选择后一定要pop掉防止队列死循环发生其次就是如果选择的中间点已经找到了最短路径我们就要跳过它然后重新从优先队列中选择。

这里我们无需判断在选了因为说过优先队列里面是混乱的我们无需考虑但是最后拿到的经判断后一定是我们想要的全部无论距离是多少直接把相应的源点距和对应的点搞进去这里相当于把我们朴素版的判断优化到了极致。

3.2代码实现展示

v[N];//表示i为始点v[i]里面的的每个pair的元素代表它的下一个点以及到达的边权

//这里的优队就是为了把遍历朴素法的dist数组的复杂直接转成靠stl容器完成选择出这个已经找到最短路径的中间点然后开始搜索继续放入队列)

//注队列中的元素不完全是某点最短路径长度是所有能到达此点的路径依靠stlpq的性质完成自己筛选出最短

//这里为了我们不仅可以知道源点到某点的最短距离以及路径故我们每次都把前驱节点推进去

pairint,

//其次就是注意外层pair顺序我们是优先以路径长短作为判断的ll和int不能颠倒与定义的vector的pair类型不同

bool

pre[N];//某点的在源点到达它最短路径上的前驱结点一直递归下去可以到达源点

void

{pq.emplace(0LL,make_pair(x,x));//把第一个推进去启动查找while

(!pq.empty())

(check[p.first])continue;//其实就是朴素版的check判断//已经确定了某点最短路径如果再次找到其前驱节点与它之间有连接那么这条路一定不是//比它短的而且已经找到了最小路径所以不能再更新dist了。

pre[p.first]

p.second;//保存其最短路径终点的前驱节点dist[p.first]

(auto

p.first));//都推进去依靠pq特性选择最短pq里是“很乱的”}}

int

z;v[x].emplace_back(make_pair(y,

z));//v[y].emplace_back(make_pair(x,

z));//双向边处理}Dijkstra(1);getdis();cout

endl;getpath(2);//等于自身可能自身成环也可能无法到达

3.3测试效果

对节点的操作需要对每个节点进行操作包括初始化、从优先队列中取出节点这部分的时间复杂度是

Dijkstra

首先我们以一道题来测试下我们写的代码当然了一般拿Dijkstra算法出题肯定朴素版大概过不了只能优先化后出场了

OJ链接蓝桥账户中心

这里如果每个点之间都是10^9那么就超越整型范围了因此我们最好用long

代码展示优先队列版

{pq.emplace(0LL,make_pair(x,x));while

(!pq.empty())

(check[p.first])continue;pre[p.first]

sourd;check[p.first]

z;v[x].emplace_back(make_pair(y,

z));}Dijkstra(1);for

相信大家肯定有类似这样的疑惑那么下面就来一一举例为大家解答疑惑

5.1为什么我们从dist中选的的最小的点dist值一定是最小源点距

其实很简单我们反证法证明一下

这里我们假设我们所选的C这个点dist里面虽然是最小的但是不是它的到A点的最短源点距。

那么肯定存在一条路A~C其中经历了B作为C的前驱结点是最短了如果存在的话B肯定没有被选到否则就与上面路重复了是一条了明显肯定A到B一定要是比选的C的dist值小但是这样我们就不会选到C了而是B与我们假设矛盾故不成立即选择其中dist值最小的点一定是最小源距已完成的点不会再更新。

5.2为什么选择最小源点距的点u去更新v再次放入v对应的dist值不一定是最小的

首先我们先选的中间点肯定是Cc和E之间然后更新D的dist值为11比100大;之后中间点又会去选C此时还会去更新D的dist值故解答标题所述疑惑。

5.3为什么每次不是在更新dist操作的时候标记1对v而是选出最小源点距的点u后给u标记1

首先我们要明白如果我们标记了某个点之后还有通往这个点的路径的时候可能是更短那么我们就无法更新了还是看图

距离10小于12故更新如果此时标记C那么当我们下一次选D会发现路径是7比之前还小但是已经标记了无法修改故会出错。

博主也写了篇Floyd算法的文章大家不懂可以去看也是通俗易懂的哦

传送门【狂热算法篇】探秘图论之

首先Floyd算法是遍历每个点作为终止点的前驱节点进行填表它进行一次就可以得到每个点到每个店之间的最小路径即是多源路径。

而Dijkstra算法它是以一个确定的源点固定好去依次找最短路径来确定源点到某点的距离认为只要是最短的那么通过它到到达源点一定是最短的是一种贪心思想忽略了边权位负数情况后面会分析即单源路径。

6.2时间复杂度

时间复杂度对于Floyd算法三层循环直接拉到了oN^3;而dijkstra算法朴素是o(N^2)优先队列优化后是o(logN)。

6.3算法实现原理

Floyd算法基于广搜动态规划实现而Dijkstra算法基于贪心广搜或优先队列实现。

6.4使用注意事项

这样我们会发现是找不到某两点之间的最小路径的因为这个环可以无限循环。

首先我们要明白它是种贪心的思路当找到我们目前认为的最小值它就会确定下来某点的最短源点距进而不再更新

D更新dist发现最小的B那么我们就会通过这种贪心思想确定B最短源点距就是2当通过D就不会再去更新B(但是此时源点距为-4小于2)这就违背了事实。

Floyd算法能用于负边但不能应用于负环

这里是因为我们会每次把每个店作为终点的前驱中间点遍历一遍然后更新一下目前的最短距离表那么到最后每个点都遍历完的时候肯定会找到最短路径此时会考虑到负边权情况但是对于负环上面也介绍了无法找出但是可以通过Bellman_Ford算法检测出来这里就不多说了。

七·实际应用场景

在计算机网络中用于计算从源路由器到其他路由器的最短路径以优化数据包的传输路径减少网络延迟和提高网络性能。

计算城市间的最短行车路线帮助规划最优的交通路径减少交通拥堵和行程时间。

7.3地图导航

计算城市间的最短行车路线帮助规划最优的交通路径减少交通拥堵和行程时间。

7.4资源分配

在资源分配问题中如电力网络中从发电站到各个用户的最短传输路径计算优化电力传输减少能源损耗。

八·本篇小结

下面基于博主自主学习了了Dijkstra算法的个人理解希望有帮助

首先我们可以如果实在理解不了就可以看一遍博主模拟的过程背一背模版上面其实也不难理解就是标记好源点然后选中间点第一次就是源点然后依次找可达点根据限定条件更新dist数组就完了朴素版对于优化版---只不过是把我们判断条件交给优先队列自己实现了大量条件个人还是觉得优化版更加舒服代码还少啊哈哈哈总之图论学习尚未结束后序博主还会进行更新的欢迎大家订阅。