Ford算法:
前面讲到Djikstra算法,它的前提是假设所有弧长均为非负值,如果允许为负值,不一定都能得到一条最短路.Ford算法是在迪克斯特拉算法的基础上稍加修改,使之可用于负长度弧的情况.
第一步和Djikstra算法一样.开始时,令d( s)=0,d(x)= (对所有不等于s的 x).y表示已着色的最后一个顶点.对始点s着色,令y=s.
对于所有各顶点(而不是未着色点)重新定义d(x)=min{ d(x),d(y)+a(y,x)},对于所有顶点x,如d(x) = ,则算法终止.即从s到任一顶点都没有路.否则,对具有d(x)最小值的顶点进行着色(不仅是未着色点).令y=x.需要注意的一点是:如果一个已着色顶点上指定的数值减小,则将与其相关的着色弧的颜色抹掉.
判断算法终止的条件:①当所有顶点都着色;②第2步不能使任一顶点上的数值减小时,算法终止.
例, 用伏特算法求从s到t的最短路 ,如右图.
第1步 开始,s着色,d( s)=0,d( a),d( t)均为
第2步 y=s 2 -2
d( a) =min{ d( a),d( s)+a(s,a)}
=min{ ,0+2 }=2
d( t) =min{ d( t),d( s)+a(s,t)} 1
=min{ ,0+1 }=1
d( t)=1为最小值,对t着色,对弧(s,t)着色.
现有最短路图是(s,t).
第3 步 不是所有顶点都已着色,不满足算法终止条件,返回第2步.
第2步 y=t
由于没有从t引出的弧,所以全部顶点数值不变.故对a点着色,同时对弧(s,a)着色.现有最短路数形图由(s,t),(s,a)组成.
第3步 满足条件①,现在看是否满足条件②返回第2步检查顶点数值是否减小.
第2步 y=a
d( t) =min{ d( t),d( a)+a(a,t)}
=min{1,2-2 }=0
d( s) =min{ d( s),d( a)+a(a,s)}
=min{0,2+ }=0
d( t)的值由1减小到0,因此将t和(s,t)抹掉颜色.现有最短路树形图仅有(s,a).
顶点t是仅有的未着色顶点,必须对t着色,同时对弧(a,t)着色.此时最短路树形图是(s,a),(a,t).
第3步 满足条件①,现在看是否满足条件②,返回第2步检查是不是有顶点的数值可减小.
第2步 y=t
由于没有从t引出的弧.所以没有再可减小的顶点数值.没有一个顶点的颜色可以抹掉.
第3步 由于所有顶点都已着色,且没有可以再减小的顶点数值,算法终止.从s到t的最短路数形图是(s,a),(a,t),其长度为2-2=0.
由前一位同学介绍过Djikstra算法的运算时间为O().在伏特算法中,对每个顶点的着色可以多到N-1次,而Djikstra算法读一每个顶点最多着色一次.由此得伏特算法在最坏情况下需要的时间为O().
疑难点:1,在什么情况下,Djikstra算法得不到一条最短路
2,当包含总长度为负值的回路时,伏特算法失败,为什么
3,为什么在伏特算法中任一个顶点着色达N次(N为图中顶点的数目)时,图中包含负回路
t
a
s
s
t
a
s
t
s
t
s
a
t