Dijkstra算法求单源最短路

 我来答
舒适还明净的海鸥i
2022-06-22 · TA获得超过1.7万个赞
知道小有建树答主
回答量:380
采纳率:0%
帮助的人:69.9万
展开全部

dijkstra算法用于求解单源最短路问题,只能求解正权图,图中有负边求出来的结果会有问题。

算法的思想就是先确定一个起点(源点),然后寻找这个点到其他所有点的距离最小值,找到一条距离最短的线路。

第一次查询这条路径一定是只有这两个点的,确定了这个点,就标记一下,说明这个已经是最短的了,接下来这个点就不参与比较了。

标记过后就把这个点延伸出去的边处理下,因为还要去选从起点到其他点的最短距离,所以要借助这个点去更新一下其他点的最小距离。因为第一次查询时只存储了与源点直连的点,有的点没有与源点直接连接,现在就可以借助这个确定的点进行间接连接。然后把其他直接连接的距离处理更新下。然后重复进行找距离源点最近的点,然后进行更新标记。

每一次循环会标记一个点,所以循环n次就能把n个点的图处理完毕。

第一行包含整数 n m

接下来 m 行每行包含三个整数 x , y , z ,表示存在一条从点 x 到点 y 的有向边,边长为 z

求解从点1到点n 的最短路径。

堆优化版要用邻接表(链式前向星)进行存图,如果是稠密图推荐用邻接矩阵存图用朴素做法。

堆优化版在算法竞赛中比较适用,可以大幅提高运行效率。

优化思路:

因为每次循环都要去找下一个距离源点最近的的点,但是朴素做法每次都要把所有点都比较判断下,如果每次当有新的距离更新了,就把这个距离装到堆中,那么就不用再去一个个比较了,直接把堆顶元素取出就行了。

dist数组存储的是从源点到其他n个点的距离,每次找的也是这个距离,一次更新一个点,更新完毕就是起点到n个点之间的最短路。

已赞过 已踩过<
你对这个回答的评价是?
评论 收起
推荐律师服务: 若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询

为你推荐:

下载百度知道APP,抢鲜体验
使用百度知道APP,立即抢鲜体验。你的手机镜头里或许有别人想知道的答案。
扫描二维码下载
×

类别

我们会通过消息、邮箱等方式尽快将举报结果通知您。

说明

0/200

提交
取消

辅 助

模 式