最短路径法的描述.doc

Dijks仃a算法基本原理如下描述：第1步开始，所有弧和顶点都未着色。对每个顶点x指定一个数d(X)，d(x)表示从s到x的最短路的长度(中间顶点均已着色)。开始时，令d(s)=O，d(x)=(对所有xs)。y表示已着色的最后一个顶点。对始点s着色，令y=s。第2步对于每个未着色顶点x，重新定义d(x)如下：d(x)=miIld(x)，d(y)+a(y，x)对于所有未着色顶点x，如d(X)=，则算法终止。因为此时从s到任一未着色的顶点都没有路。否则，对具有d伍)最小值的未着色顶点x进行着色。同时把弧(y，x)着色(指向顶点x的弧只有一条被着色)。令烨。第3步如果顶点t已着色，则算法终止。这时已找到一条从s到t的最短路。如果t未着色，则转第2步。注意：已着色的弧不能构成一个圈，而是构成一个根在s的树形图，此树形图称为最短路树形图。若x是最短路树形图中的任一顶点，则从s到x的唯一的一条路是从s到x的最短路。这个算法可以看成是根在顶点s的树形图的生长过程。一旦到达顶点t，生长过程就停止。下面举例说明用狄克斯特拉算法找出从源点s到终点t的最短路径，如图图31所示。14第l步开始，只有s着色，d(s)=o。而且对于所有xs，d(x)=。第2步y=sd(a)司：血(d(a)，d(s)+a(s，a)黾r血，O+4)=4d(b)=nliIld(b)，d(s)+a(s，b)=milloo，O+7)=7d(c)司血d(c)，d(S)+s，c)鼍11i11，O+3)=3d(d)气nilld(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)=说i11d(a)，d(c)+a(c，a)吼in4，3+)=4d(b)=硼血d(b)，d(c)+a(c，b)鼍nin7，3+)=7d(d)=mind(d)，d(c)+a(c，d)=min，3+3=6d(t)2r近nd(t)，d(c)+c，t)砌i11，3+)=由于d(a)_4是最小值，所以对顶点a着色，并对确定d(a)的弧(s，a)着色。见图b)。第3步顶点t未着色，返回第2步。第2步)，=ad(b)=姐ind(b)，d(a)+a(a，b)铀in7，4+3)=7d(d)=姐ind(d)，d(a)+a(a，d)=min6，4+2)=6d(t)=：rnind(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)=mind(b)，d(d)+d，b) 砒7，6+)=7d(t)=mind(t)，d(1)+d，t)爿niIl，6+2)=8d(b)=7是最小值，对点b着色，对确定d(b)的弧(s，b)着色。见图d)。第3步顶点t未着色，返回第2步。17第2步v=bd(t)=刁nind(t)，d(b)+a(b，t)可niIl8，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是两点之间的最小费用。图32 Dijkstra的流程图从上面Dijkstra算法的描述和实现步骤可以看出，D破stra算法思路简明，实现起来非常容易，但由于它存在3个循环，第一个循环的时间复杂度为0(以)，第2、3个循环为嵌套循环，它们的时间复杂度也为0(挖)，第2、3循环之间是顺序方式执行，没有嵌套关系，它们是第一个循环的嵌套。因此，当求解一个节点到另一个节点的最短路径时，采用Dijkstra算法其时间复杂度为0(形)木0(终)，即为D(以2)。当图(或网络)规模较大时，Dijkstra算法的时间复杂度和空间复杂度都19会急剧增加，算法的计算量大，时间花费多。在现实中，网络模型的规模常常较大，顶点数多达上千或上万，并且由于导航系统一般要求计算出到目的地点最佳路线的时间应该在卜3s内，这就决定了最短路径问题的实现应该是高效率的。从以上经典Dijks仃a算法的介绍得知，该算法对所有的数据