得到P标号的点都有T标号。算法每一步都把某一点的T标号改为P标号,当终点vt得到P标号时,全部计算结束。对于有n个顶点的图,最多经n-1步就可以得到从始点到终点的最短路。步骤:(1)给vs以P标号,P(vs)=0,其余各点均给T标号,T(vi)=+∞。(2)若vi点为刚得到P标号的点,考虑这样的点vj:(vi,vj)属于E,且vj为T标号。对vj的T标号进行如下的更改:T(vj)=min[T(vj),P(vi)+lij](3)比较所有具有T标号的点,把最小者改为P标号,即:P(vi)=min[T(vi)]当存在两个以上最小者时,可同时改为P标号。若全部点均为P标号则停止。否则用vi代替vi转回(2)。得知了Dijkstra算法的基本思路和基本步骤,下面举个实际应用的例子。例:某工厂使用一台设备,每年年初工厂都要作出决定,如果继续使用旧的,要付维修费;若购买一台新设备,要付购买费。试制订一个5年的更新计划,使总支出最少。若已知设备在各年的购买费,及不同机器役龄时的残值与维修费,如下表所示:项目第1年第2年第3年第4年第5年购买费1112131414机器役龄0~11~22~33~44~5维修费5681118残值43210解:把这个问题化为最短路问题。用点vi表示第i年年初购进一台新设备,虚设一个点v6表示第5年年底。边(vi,vj)表示第i年初购进的设备一直使用到第j年年初(即第j—1年年底)。边(vi,vj)上的数字表示第i年初购进设备,一直使用到第j年初所需要支付的购买、维修的全部费用(可由表中数据计算得到)。例如(v1,v4)边上的28是第一年初购买费11加上三年的维修费5,6,8,减去3年役龄设备的残值2;(v2,v4)边上的20是第二年初购买费12加上使用两年的设备维修费5,6减去两年役龄设备的残值3。这样设备更新问题就变为:求从v1到v6的最短路问题,计算过程如下:
全文预览
