数学建模社区-数学中国

标题: 最短路径dijkstra算法 [打印本页]
作者: 2744557306    时间: 2023-8-5 15:09
标题: 最短路径dijkstra算法
最短路径
当图为带权图时，把一个从顶点V0到图中任意顶点的路径所经过边的权值之和，定义为该路径的带权长度，把带权路径长度最短的那条路径称为最短路径。
对于最短路径有下面两种说法：1 L! }6 }5 j" t% g5 {8 Z! A8 g
! d5 _0 e% M( ~; x3 Z  y6 [9 |& `
在最短路径中遇到不同的问题我们应该用那种方法呢？具体方法如下图所示：
) V; M9 \) D' I$ j( h- F# `/ j" v0 F
首先我们来看最短路径dijkstra算法，他是寻找单源最短路径的。我们需要3个数组final[5],dist[5],path[5]。具体含义如下所示：其中最短路径长度是v0到该节点的最短路径
. _6 x7 x$ O% P; }& m& M5 B9 H+ S- O, _( u
首先，我们从v0开始，v0可以到v1与v4。我们先把他们的路径长度提案先到最短路径长度上，并修改前驱，前驱为v0。此时的v1与v4都没有找到最短路径，只有v0找到了到v0的最短距离，距离为0。在第一轮中循环遍历所有节点，找到没有确定最短路径且dist最小的顶点我们选取v4，说明找到了v0到v4的最短路径，(如果不是最短路径他只能走v1那条路线，但是他已经超过了5，走v1路线一定不是最短的)。
对其他final为false的节点进行更新，经过v4出去的节点有三个，将其全部更新，将v4到其他三个节点与v4记录中的最短路径相加，如果路径大于记录的路径长度则不用更新。最终更新结果如下图所示：
此时我们最短路径长度已经有两个确认了，寻找剩下的长度最小的V3，将v3的final改为true，对v1，v2的最短路径进行更新。其中v3指向的节点只有v2，v3的最短路径为7，7+6=13<14。将v2节点的最短路径更改为13，且前去改为v3
之后再次寻找最小长度，为v1，将v1的final改为true，从v1指出的阶段有v2，8+1=9<13.更新最后节点v2节点的最短路径，将其final改为true，更新其前驱为v1，结果如下：
可以观察到从v0到v1的最短距离为8，到v2的最短距离为9，v3为7，v4为5。那么如何寻找路径呢？已知到v2的长度为9，我们寻找他的前驱，前驱为1，v1的前驱为v4，v4的前驱为v0，我们就可以得到它的最短路径了，v0 ->v4 ->v1->v2。
) ~) J- d! a% m" d6 s
由于图片上传有限制，图片都在附件中
; u2 j  t" Q: Q8 A6 h# c

- L: Y7 b5 ]( G$ q$ r

最短路径djkstral.docx

855.07 KB, 下载次数: 0, 下载积分: 体力 -2 点
作者: 旺旺碎冰冰    时间: 2023-9-1 22:07
谢谢分享
( S0 a: a- w3 D9 a) h( V) f



欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5