最短路的算法--Dijkstra算法.doc

最短路的算法--Dijkstra算法
在图G中,给定s和t两个顶点。从s到t可以有多条路径,从这多条路中找出长度最小的路,这样的路称为从s到t的最短路。设每条弧的长度均为非负值。
下面的算法是由狄杰斯特拉(Dijkstra,1959)提出的,其想法是:设已知图中最接近于顶点s的m个顶点以及从顶点s到这些顶点中每一个顶点的最短路(从s到其本身的最短路是零路,即没有弧的路,其长度为0)。对顶点s和这m个顶点着色。然后,最接近于s的第m+1个顶点可如下求之:
对于每一个未着色的顶点y,考虑所有已着色顶点x,把弧(x,y)接在从s到x的最短路后面,这样就得到从s到y的m条不同路。从这m条路中选出最短的路,它就是从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)=∞(对所有x≠s)。y表示已着色的最后一个顶点。对始点s着色,令y=s。
第2步对于每个未着色顶点x,重新定义d(x)如下:
d(x)=min{ d(x),d(y)+a(y,x)} 公式
对于所有未着色顶点x,如d(x)=∞,则算法终止。因为此时从s到任一未着色的顶点都没有路。否则,对具有d(x)最小值的未着色顶点x进行着色。同时把弧(y,x)着色(指向顶点x的弧只有一条被着色)。令y=x。
第3步如果顶点t已着色,则算法终止。这时已找到一条从s到t的最短路。如果t未着色,则转第2步。
注意:已着色的弧不能构成一个圈,而是构成一个根在s的树形图,此树形图称为最短路树形图。若x是最短路树形图中的任一顶点,则从s到x的唯一的一条路是从s到x的最短路。这个算法可以看成是根在顶点s的树形图的生长过程。一旦到达顶点t,生长过程就停止。
例:给定有向图如下图所示,用狄克斯特拉算法找出从s到t的最短路径。
第1步 开始,只有s着色,d(s)=0。而且对于所有x≠s,d(x)=∞。
第2步 y=s
d(a)=min{ d(a), d(s)+a(s,a)}
=min{∞,0+4}=4
d(b)=min{ d(b), d(s)+a(s,b)}
=min{∞,0+7}=7
d(c)=min{ d(c), d(s)+a(s,c)}
=min{∞,0+3}=3
d(d)=min{ d(d), d(s)+a(s,d)}
=min{∞,0+∞}=∞
d(t)=min{ d(t), d(s)+a(s,t)}
=min{∞,0+∞}=∞
由于d(c)=3是最小值,所以对c点着色,并对确定d(c)的弧(s,c)着色。见图a)。
第3步 顶点t未着色,返回第2步 。
第2步 y=c
d(a)=min{ d(a), d(c)+a(c,a)}
=min{4,3+∞}=4
d(b)=min{ d(b), d(c)+a(c,b)}
=min{7,3+∞}=7
d(d)=min{ d(d),