（简答题）

求下面网络节点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。

答案解析

略

相似试题

（判断题）
网络计划图中的关键路线，必是然从最初节点到最终节点的一条最短路线。
答案解析
（简答题）
简述网络基本要素组成。(1)节点(2)连通路线或链(3)中心(4)障碍
答案解析
（判断题）
工程网络图中，只能有一个开始节点，但可以有多个结束节点。
答案解析
（判断题）
若已求得网络最大流，已标号节点的集合和未标号节点的集合给出了网络的最小割集。
答案解析
（名词解析）
节点式网络图
答案解析
（简答题）
已知下列问题的最优解为X*=（1/7，11/7），用互补松弛定理求其对偶问题的最优解。
答案解析
（简答题）
某地的电力公司有三个发电站，它们负责5个城市的供电任务，其输电网络如图所示。由图可知，城市8由于经济的发展，要求供应电力65MW，三个发电站在满足城市4、5、6、7的用电需要量后，它们还分别剩余15MW、10MW、40MW，输电网络剩余的输电能力见图4节点上是数字。三个发电站在满足城市4、5、6、7的用电需要量后，剩余发电能力共有65MW，与城市8的用电量刚好相等。问：（1）输电网络的输电能力是否满足输电65MW的电力；（2）如不满足，需要增建或改建那些输电线路？
答案解析
（单选题）
在求最大流量的问题中，已知与起点相邻的三节点单位时间的流量分别为10，12，15，则终点单位时间输出的最大流量应（）
答案解析
（填空题）
双代号网络计划图在计算时间参数时，可分为（）计算法和节点计算法。
答案解析