第九章网络优化模型.pptVIP

车龄每年的维护费用交易费用01234520004000500090001200070006000200010000c12=2+12-7=7c13=2+4+12-6=12c14=2+4+5+12-2=21c15=2+4+5+9+12-1=31c16=2+4+5+9+12+12-0=44c23=2+12-7=7c24=2+4+12-6=12c25=2+4+5+12-2=21c26=2+4+5+9+12-1=31c34=2+12-7=7c35=2+4+12-6=12c36=3+4+5+12-2=21c45=2+12-7=7c46=2+4+12-6=12c56=2+12-7=71234567777712121221313144122121第三节最短路问题第29页，共70页，星期日，2025年，2月5日Dijkstra最短路算法：假设每个弧的权是非负的，即wij≥0，给每个支点vi记一个数(称标号)，标号分临时性标号T和永久性标号P，永久性标号表示从v1到该点vi的最短路权，得到永久性标号的不再改变标号，临时性标号表示从开始点v1到该点vi的最短路权的上界，算法每一步都把某一点的T标号改为P标号，开始时给初始支点v1标号记为0，即P(v1)=0，其他支点(记为临时性标号)的标号记为+∞，即T(vi)=+∞,若vi点是刚得到P标号的点，考虑L中与vi点相连的弧(vi,vj)且vj是T标号，对vj的标号进行如下更改：T(vj)=min{T(vj),P(vi)+Wij}比较所有具有T标号的点，把最小者改为P标号，当存在两个以上最小者时，可以同时改为P标号，直到全部点均改为P标号为止第三节最短路问题第30页，共70页，星期日，2025年，2月5日例：从发电厂（记为节点1）向某城市（记为节点6）输送电，必须通过中转站（记为节点2，3，4，5）转送。图给出了两节点间的距离。电力公司希望选择合适的中转站，使从电厂到城市的传输路线最短。即从节点1到节点6的最短路径。这就是一个最短路问题。第三节最短路问题第31页，共70页，星期日，2025年，2月5日1325464332322第0步：P(1)=0,T(i)=+∞；第1步：与1相连的标号为2,3，均是T标号，修改2,3的标号，T(2)=min{T(2),P(1)+w12}=4,T(3)=3；在所有的T标号中，3的标号最小，改3的标号为P(3)=3；第2步：修改与3相连的T标号；在所有剩下的T标号中，2的标号最小，改为P(2)=4；第3步：修改与2相连的T标号；在所有剩下的T标号中，5的标号最小，改为P(5)=6；第4步：修改与5相连的T标号；在所有剩下的T标号中，4的标号最小，改为P(4)=7；第5步：修改与4相连的T标号；只剩下节点6是T标号，修改6的标号，P(6)=8。从节点6开始回退，得到最短路。P(1)=0T(3)=+∞T(2)=+∞T(3)=3T(5)=+∞P(3)=3T(5)=6T(2)=4T(4)=+∞T(6)=+∞P(2)=4T(4)=7P(5)=6T(6)=8P(4)=7P(6)=8P(6)=8P(5)=6P(3)=3P(1)=0第三节最短路问题第32页，共70页，星期日，2025年，2月5日P(1)=0T(2)=+∞T(4)=+∞T(3)=+∞T(5)=+∞T(6)=+∞T(7)=+∞第2步：与4相连的标号为2,3,5,6，均是T标号，修改2,3,5,6的标号，T(2)=min{T(2),P(4)+w42}=4,T(3)=min{T(3),P(4)+w43}=3T(5)=min{T(5),P(4)+w45}=7T(6)=min{T(6),P(4)+w46}=9在所有的T标号中，3的标号最小，改3的标号为P(3)=3；T(2)=4T(3)=3T(4)=2P(4)=2第1步：与1相连的标号为2,3，4，均是T标号，修改2,3,4的标号，T(2)=min{T(2),P(1)+w12}=4,T(3)=min{T(3),P(1)+w13}=3T(4)=min{T(4),P(1)+w14}=2在所有的T标号中，4的标号最小，改4的标号为P(4)=2；T(2)=4T(3)=3T(5)=7T(6)=9第3步：与3相连的是T标号,为5，修改5的标号，T(5)=min{T(5),P(3)+w35}=6在所有的T标号中，2的标号最小，改2的标号为P(2