取上表的v1行数据即为 d11j= w1j ；第一次迭代是 d11j列的元素与下表中第1-6列对应元素 相加取最小，得到 d21j列；其余函数迭代过程以此类推。
由于 d31j= d41j，则迭代结束，此时 d31j列的各元素，即为v1到其余各点的最短路权。再根据 d31j列各元素的来源，可以追踪最短路径。例如，追踪 v1到v6的最短路径，对于d316=6， d214+w46=4+2=6计算而得，则v6的前一个点是v4；再根据 d214=4进行追踪， 这是由d124+w24=1+3=4计算而得，则 v4的前一个点是 v2；再看 d112=1,这是由w12=1 而得的，所以最短路径为v1→v2→v4→v6。 5.（1）将问题转换成最短路问题，如
（2）给网络始点v1标号(v1,0) ，并在标号下面画横线表示为永久标号；并给从v1出发的各弧的点vj赋予临时标号(v1,v1j)。
在所有临时标号中选择路权最小者，即结点v2，将v2的临时标号变为永久标号，在标号下画横线。然后，考察从v2出发的各弧的点vj的 临 时 标 号 ： 结 点 v3的路权 d3= min{22,d1+w15} = min{22,16 +17} = 22 ，则v3临时标号不变；同理，对于结点v4、v5临时标号均不变。
依此类推，重复上述标号过程。当所有标号都是永久标号，即每一个标号下都画上横线时，则标号过程结束。v5的后一个标号为v1到v5的最短路权，即41；根据v5的另一个标号反向追踪求得v1到v5的最短路径为{v1,v5}。
费用最小的方案为：第一年购置设备，此后四年不再更新。 6. 根据题意，可以画出如下的网络图。
从表中可以看出，方案路线v1→v2→v4→v10→v22与v1→v2→v4→v11→v22最短，对应的费用均为130。 7.（1）首先设置初始流量，如下图：
逐步增加流量，如下图：
弧 (v4,v7) 、 (v6,v7) 、 (v5,v7) 均为饱和流，不能再增加流量，因此得到 v1到 v7的最大流。（ 2 ） 由 于 弧(v
*
4,v7) 、 (v6,v7) 、 (v5,v7) 都 是 饱 和 弧 ， 所 以 从 此 截 开 ， S={v1,v2,v3,v4,v5,v6}，
={v7 }，得
到最小截集 (S*,
)= {(v4,v7) 、 (v6,v7) 、 (v5,v7)}，其截量为 2+3+2=7。
8.（1）所给流是否是可行流。即
①容量限制：对每条弧 (vi, vj) ∈ A ，都有 0 ≤ xij≤ bij； ②平衡条件：中间各点的流出量等于其流入量。 （2）画出赋权有向图，如下：
存在负回路v1→v2→v3，总权数为 2-6-3=-7。则目前的网络流需要调整。
,进行流量调整，弧(v1, v2) 存在负回路方向一致与负回路方向一致，
则其流量调整为 x12+θ=2+1=3；而弧(v3,v2) 与负回路方向相反，则其流量调整为 x32? θ =1-1=0；弧 (v1,v3)
与负回路方向相反，则其流量调整为 x13- θ =4-1=3。调整后的网络为：