内容发布更新时间 : 2024/5/18 8:57:23星期一 下面是文章的全部内容请认真阅读。

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