求下面网络节点1到节点7的最短路径。_睦霖题库

简答题求下面网络节点1到节点7的最短路径。

正确答案：用T、P标号算法：
①给v₁点标P标号，其他点标T标号，为＋∞。
②从v₁点出发，修改v₂、v₃、v₄点的T标号，并把其中最小者改为P标号。
T（v₂）=4=P（v₂），T（v₃）=6，T（v₄）=5= P（v₄）。
③从刚刚获得P标号的点v₂出发，可达v₃，v₅（与其相邻的且还未获得P标号的点），修改其T标号，并把最小T标号v₃，v₅改为P标号。
T（v₃）=min{6，p（v₂）+d₂₃}=min{6，4+1}=5=P（v₃），T（v₅）=11。
④依此类推，各点的P标号如图所示。
从v1到v7的最短路为：v₁→v₂→v₃→v₅→v₇或v₁→v₂→v₃→v₆→v₅→v₇，距离为16。
答案解析：
关注下方微信公众号，在线模考后查看

热门试题