（设备更新问题）某企业使用一台设备。每年年初，企业都要作出决定，是继续使用旧设备，付维修费，或是购买新设备，付购买费。试制定一个 5 年的更新计划，使总支出最少。


构造一个有向图 G=(V,E)。顶点 vi 表示第 i 年初时点 (i=1,2,3,4,5,6) ,用 v6 表示第 5 年底。边 vivj 表示第 i 年初购进设备，一直用到第 j 年初（第 j-1 年底）。


边 vi vj 上的权表示第 i

（设备更新问题）某企业使用一台设备。每年年初，企业都要作出决定，是继续使用旧设备，付维修费，或是购买新设备，付购买费。试制定一个 5 年的更新计划，使总支出最少。

 
构造一个有向图 G=(V,E)。顶点 vi 表示第 i 年初时点 (i=1,2,3,4,5,6) ,用 v6 表示第 5 年底。边 vivj 表示第 i 年初购进设备，一直用到第 j 年初（第 j-1 年底）。


边 v_i v_j 上的权表示第 i 年初购进设备费和一直使用到第 j 年初的全部费用。例如 V₁ 到 V₆ 的 59 表示购买费用 11，维修费用＝最初一年的维修费 5+使用该设备第二年时的维修费 6+使用该设备第三年时的维修费 8+使用该设备第四年时的维修费 11+使用该设备第五年时的维修费 18＝5+6+8+11+18＝48。所以总费用为 11+48＝59再比如 V₁ 到 V₃，V₃ 到 V₆，其总费用＝22+31＝53，表示第一年购买，使用两年，然后再购买使用三年，其
总费用＝11+5+6+12+5+6+8＝22+31＝53
 
于是，v₁ 到 v₆ 的每一条路都是一个可行方案。采用标注的办法，其中，V₁ 到 V₄（权重为 30），V₄ 到 V₆（权重为 23）是最小路径。或者 V₁ 到 V₃（权重为 22），V₃ 到 V₆（权重为 31）是最小路径。