迪杰斯特拉(Dijkstra)算法详解

Python013

迪杰斯特拉(Dijkstra)算法详解,第1张

Dijkstra算法设置一个集合S记录已求得的最短路径的顶点,初始时把源点v0放入S,集合S每并入一个新顶点vi,都要修改源点v0到集合V-S中顶点当前的最短路径长度值。

本例基于邻接矩阵存储的图。

在构造的过程中要设置三个辅助数组:

假设从顶点0出发,即v0=0,集合S最初只包含顶点0,邻接矩阵 edge[][] 表示带权有向图, edge[i][j] 表示有向边<i,j>的权值,若不存在有向边<i,j>,则 edge[i][j] 为∞。

Dijkstra算法的步骤如下:

顶点数:5,弧数:10

顶点编号:A B C D E

邻接矩阵:

参考结果:

最近也看到这个算法,不过主要是通过C语言介绍的,不太一样,但基本思想差不多。下面只是我个人的看法不一定准确。

Dijkstra算法主要解决指定某点(源点)到其他顶点的最短路径问题。

基本思想:每次找到离源点最近的顶点,然后以该顶点为中心(过渡顶点),最终找到源点到其余顶点的最短路。

t=1:令源点(v_0)的标号为永久标号(0,λ)(右上角加点), 其他为临时(+无穷,λ). 就是说v_0到v_0的距离是0,其他顶点到v_0的距离为+无穷。t=1时,例5.3上面的步骤(2)(3)并不能体现

t=2:第1步v_0(k=0)获得永久标号,记L_j为顶点标号当前的最短距离(比如v_0标号(0,λ)中L_0=0), 边(v_k,v_j)的权w_kj. 步骤(2)最关键,若v_0与v_j之间存在边,则比较L_k+w_kj与L_j, 而L_k+w_kj=L_0+w_0j<L_j=+无穷。

这里只有v_1,v_2与v_0存在边,所以当j=1,2时修改标号, 标号分别为(L_1, v_0)=(1, v_0), (L_2, v_0)=(4, v_0), 其他不变。步骤(3)比较所有临时标号中L_j最小的顶点, 这里L_1=1最小,v_1获得永久标号(右上角加点)。

t=3: 第2步中v_1获得永久标号(k=1), 同第2步一样,通过例5.3上面的步骤(2)(3),得到永久标号。 步骤(2),若v_1与v_j(j=2,3,4,5(除去获得永久标号的顶点))之间存在边,则比较L_1+w_1j与L_j。这里v_1与v_2,v_3,v_,4存在边,

对于v_2, L_1+w_12=1+2=3<L_2=4, 把v_2标号修改为(L_1+w_12, v_1)=(3, v_1)

对于v_3, L_1+w_13=1+7=8<L_3=+无穷, 把v_3标号修改为(L_1+w_13, v_1)=(8, v_1)

对于v_4, L_1+w_14=1+5=6<L_4=+无穷, 把v_4标号修改为(L_1+w_14, v_1)=(6, v_1)

v_5与v_1不存在边,标号不变。步骤(3), 找这些标号L_j最小的顶点,这里v_2标号最小

t=4: k=2, 与v_2存在边的未获得永久标号的顶点只有v_4, 比较L_2+w_24=3+1=4<L_4=6, 把v_4标号修改为(L_2+w_24, v_2)=(4, v_2)其他不变。步骤(3), L_4=4最小。

t=5: k=4, 同理先找v_4邻接顶点,比较,修改标号,找L_j最小

t=6: 同理

啰嗦的这么多,其实步骤(2)是关键,就是通过比较更新最短路径,右上角标点的就是距离源点最近的顶点,之后每一步就添加一个新的”源点”,再找其他顶点与它的最短距离。

迪杰斯特拉算法(Dijkstra)(百度百科):

http://baike.baidu.com/link?url=gc_mamV4z7tpxwqju6BoqxVOZ_Z7fv8zCUwo7u9LWzeBLl1eV4twGEWLbvd8HjQO6VAvwTs0EcQkISDcezZ27QGWyprSmKlJjosbPNcGKtLYJ5GJsJT6U28koc_FwAlNJAjrVKYUcp3z7bmKewSxlTX8SA0uWKNcu0f0gHmpGa3#4

里面有个动图,更形象地说明了该算法的过程。(其中每次标注的一个红色顶点out就和你的这本书中获得永久标号是相似的)