《管理运筹学》历年模拟试卷(一)及答案

T?v2??min?T?v2?,P?v1??w12?

min??,0?5??5 = T?v3??min?T?v3?,P?v1??w13? =

min??,0?2??2

所有T标号中,T(v3)最小,令P(v3)=2 第二步:v3是刚得到的P标号,考察v3

?v3,v4?,?v3,v6??A,且v5,v6是T标号

T?v4??min??T?v4?,P?v3??w34??min??,2?7??9 = T?v6??min??,2+4?=6

所有T标号中,T(v2)最小,令P(v2)=5 第三步:v2是刚得到的P标号,考察v2

T?v4??min??T?v4?,P?v2??w24??

=

min?9,5?2??7

T?v5??min??T?v5?,P?v2??w25?? =

min??,5?7??12

所有T标号中,T(v6)最小,令P(v6)=6 第四步:v6是刚得到的P标号,考察v6

T?v4??min??T?v4?,P?v6??w64??=

min?9,6?2??7

T?v5??min??T?v5?,P?v6??w65?? =

min?12,6?1??7

T?v7??min??T?v7?,P?v6??w67?? 所有T标号中,T(v4),T(v5)同时标号,令P(v4)=P(v5)=7

第五步:同各标号点相邻的未标号只有v7

T?v7??min?T?v7?,P?v5??w57?

min?12,7?3??10 =

至此:所有的T标号全部变为P标号,计算结束。故v1至v7的最短路为10。

6

min??,6?6??12

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4