《最短路的算法Dijkstra算法》由会员分享，可在线阅读，更多相关《最短路的算法Dijkstra算法（5页珍藏版）》请在金锄头文库上搜索。
1、=J最短路的算法-Dijkstra 算法在图G中，给定s和t两个顶点。从s至Ut可以有多条路径，从这多条路中找出长度最 小的路，这样的路称为从s到t的最短路。设每条弧的长度均为非负值。下面的算法是由狄杰斯特拉(Dijkstra,1959)提出的，其想法是：设已知图中最接近于 顶点s的m个顶点以及从顶点s到这些顶点中每一个顶点的最短路(从s到其本身的最短路 是零路，即没有弧的路，其长度为0)。对顶点s和这m个顶点着色。然后，最接近于s的 第 m+1 个顶点可如下求之：对于每一个未着色的顶点y，考虑所有已着色顶点x,把弧(x, y)接在从s到x的最 短路后面，这样就得到从s到y的m条不同路。从这m
2、条路中选出最短的路，它就是从s 到y的最短路。相应的y点就是最接近于s的第m+1个顶点。因为所有弧的长度都是非负 值，所以从s到最接近于s的第m+1个顶点的最短路必然只使用已着色的顶点作为中间顶 点。从m=0开始，将这个过程重复进行下去，直至求得从s到t的最短路为止。 算法：狄杰斯特拉最短路算法第1步开始，所有弧和顶点都未着色。对每个顶点x指定一个数d(x), d(x)表示从s到x 的最短路的长度(中间顶点均已着色)。开始时，令d(s)=0, d(x)=g(对所有xMs)。y表示 已着色的最后一个顶点。对始点s着色，令y=s。第2步 对于每个未着色顶点x,重新定义d(x)如下：d(x)=min
3、 d(x)， d(y)+a(y， x)公式对于所有未着色顶点x,如d(x)=g，则算法终止。因为此时从s到任一未着色的顶点都没 有路。否则，对具有d(x)最小值的未着色顶点x进行着色。同时把弧(y, x)着色(指向顶点 x 的弧只有一条被着色)。令 y=x。第3步 如果顶点t已着色，则算法终止。这时已找到一条从s到t的最短路。如果t未着色， 则转第2 步。注意：已着色的弧不能构成一个圈，而是构成一个根在s的树形图，此树形图称为最短路树 形图。若x是最短路树形图中的任一顶点，则从s到x的唯一的一条路是从s到x的最短路。 这个算法可以看成是根在顶点s的树形图的生长过程。一旦到达顶点t,生长过程就停
4、止。例：给定有向图如下图所示，用狄克斯特拉算法找出从s到t的最短路径。3a247t2323ca第1步 开始，只有s着色，d(s)=O。而且对于所有xMs, d(x)=r 第 2 步 y=sd(a)=min d(a), d(s)+a(s,a)=min8,0+4=4 d(b)=min d(b), d(s)+a(s,b)=min8,0+7=7 d(c)=min d(c), d(s)+a(s,c)=min8,0+3=3 d(d)=min d(d), d(s)+a(s,d)=min 8,0+8 =8 d(t)=min d(t), d(s)+a(s,t)=min8,0+8=8由于d(c)=3是最小值，所以
5、对c点着色，并对确定d(c)的弧(s,c)着色。见图a)。 第 3 步 顶点 t 未着色，返回第 2 步 。第 2 步 y=cd(a)=min d(a), d(c)+a(c,a)=min4,3+8=4 d(b)=min d(b), d(c)+a(c,b)=min7,3+8=7d(d)=min d(d), d(c)+a(c,d)=min8,3+3=6 d(t)=min d(t), d(c)+a(c,t)=min8,3+8=8由于d(a)=4是最小值，所以对顶点a着色，并对确定d(a)的弧(s,a)着色。见图b)。 第 3 步 顶点 t 未着色，返回第 2 步 。d(b)=min d(b), d(
6、a)+a(a,b)=min7,4+3=7d(d)=min d(d), d(a)+a(a,d)=min6,4+2=6d(t)=min d(t), d(a)+a(a,t)=min 8,4+8 =8d(d)=6是最小值，对d着色，确定d(d)的弧有两条(即(c,d)和(a,d),可任选其中的一条，对其着色，我们选(c,d)。见图c)。 第3步顶点t未着色，返回第2步。C)第2 步 y=dd(b)=min d(b), d(d)+a(d,b)=min7,6+8 =7d(t)=min d(t), d(d)+a(d,t)=min8,6+2=8d(b)=7是最小值，对点b着色，对确定d(b)的弧(s,b)着色。见图d)。第2步 y=b d(t)=min d(t), d(b)+a(b,t)=min8,7+2=8对点t及弧(d,t)着色。最终的最短路树形图由弧(s,c)(s,a)(c,d)(s,b)和(d,t)组成，见图e)。 从s到t的最短路由弧(s,c)(c,d)和(d,t)组成，其长度为3+3+2=8。第5页共5页
