最短路径法的描述

《最短路径法的描述》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Dijks仃a算法基本原理如下描述：第1步开始，所有弧和顶点都未着色。对每个顶点x指定一个数d(X)，d(x)表示从s到x的最短路的长度(中间顶点均已着色)。开始时，令d(s)=O，d(x)=∞(对所有x≠s)。y表示已着色的最后一个顶点。对始点s着色，令y=s。第2步对于每个未着色顶点x，重新定义d(x)如下：d(x)=miIl{d(x)，d(y)+a(y，x))对于所有未着色顶点x，如d(X)=∞，则算法终止。因为此时从s到任一未着色的顶点都没有路。否则，对具有d伍)最小值的未着色顶点x进行着色。同时把弧(y，x)着色(指向顶点

2、x的弧只有一条被着色)。令烨。第3步如果顶点t已着色，则算法终止。这时已找到一条从s到t的最短路。如果t未着色，则转第2步。注意：已着色的弧不能构成一个圈，而是构成一个根在s的树形图，此树形图称为最短路树形图。若x是最短路树形图中的任一顶点，则从s到x的唯一的一条路是从s到x的最短路。这个算法可以看成是根在顶点s的树形图的生长过程。一旦到达顶点t，生长过程就停止。下面举例说明用狄克斯特拉算法找出从源点s到终点t的最短路径，如图图3．1所示。14第l步开始，只有s着色，d(s)=o。而且对于所有x≠s，d(x)=∞。第2步y=sd(a

3、)司：血(d(a)，d(s)+a(s，a))黾r血{∞，O+4)=4d(b)=nliIl{d(b)，d(s)+a(s，b))=mill{oo，O+7)=7d(c)司血{d(c)，d(S)+《s，c)}鼍11i11{∞，O+3)=3d(d)气nill{d(d)，d(s)+a(s，d))=Ⅱlin{∞，O+∞}=ood(t)=加血{d(t)，d(s)+a(s，t))可11in{。o，O+∞}=oo由于d(c)-3是最小值，所以对c点着色，并对确定d(C)的弧(S，c)着色。见图第3步顶点t未着色，返回第2步。a)15第2步)，=cd(a

4、)=说i11{d(a)，d(c)+a(c，a))吼in{4，3+∞)=4d(b)=硼血{d(b)，d(c)+a(c，b))鼍nin{7，3+∞)=7d(d)=min{d(d)，d(c)+a(c，d))=min{∞，3+3}=6d(t)2r近n{d(t)，d(c)+《c，t))砌i11{∞，3+∞)=∞由于d(a)_4是最小值，所以对顶点a着色，并对确定d(a)的弧(s，a)着色。见图b)。第3步顶点t未着色，返回第2步。第2步)，=ad(b)=姐in{d(b)，d(a)+a(a，b))铀in{7，4+3)=7d(d)=姐in{d(d

5、)，d(a)+a(a，d))=min{6，4+2)=6d(t)=：rnin{d(t)，d(a)+a(a，t))吼in{∞，4+o。)=∞d(d)=6是最小值，对d着色，确定d(d)的弧有两条(即(c，d)和(a，d))，可任选其中的一条，对其着色，我们选(c，d)。见图c)。第3步顶点t未着色，返回第2步。16第2步y=dd(b)=min{d(b)，d(d)+《d，b))砒{7，6+∞)=7d(t)=min{d(t)，d((1)+《d，t))爿niIl{∞，6+2)=8d(b)=7是最小值，对点b着色，对确定d(b)的弧(s，b)着

6、色。见图d)。第3步顶点t未着色，返回第2步。17第2步v=bd(t)=刁nin{d(t)，d(b)+a(b，t))可niIl{8，7+2}=8对点t及弧(d，t)着色。最终的最短路树形图由弧(s，c)(s，a)(c，d)(s，b)和(d，t)组成，见图e1。从s到t的最短路由弧(s，c)(c，d)和(d，t)组成，其长度为3+3+2=8。通过以上的过程就能够找到一条最短路径。18此算法可以用以下流程图来描述，其中COST是两点之间的最小费用。图3—2Dijkstra的流程图从上面Dijkstra算法的描述和实现步骤可以看出，D破s

7、tra算法思路简明，实现起来非常容易，但由于它存在3个循环，第一个循环的时间复杂度为0(以)，第2、3个循环为嵌套循环，它们的时间复杂度也为0(挖)，第2、3循环之间是顺序方式执行，没有嵌套关系，它们是第一个循环的嵌套。因此，当求解一个节点到另一个节点的最短路径时，采用Dijkstra算法其时间复杂度为0(形)木0(终)，即为D(以2)。当图(或网络)规模较大时，Dijkstra算法的时间复杂度和空间复杂度都19会急剧增加，算法的计算量大，时间花费多。在现实中，网络模型的规模常常较大，顶点数多达上千或上万，并且由于导航系统一般要求计

8、算出到目的地点最佳路线的时间应该在卜3s内，这就决定了最短路径问题的实现应该是高效率的。从以上经典Dijks仃a算法的介绍得知，该算法对所有的数据都作循环比较1241，因此在数据量大的情况下，严重影响计算的速度。在导航系统的最短路径寻