第十讲 最短路模型
（教材：第十章 最短路模型）
三. 最短路模型及可以化为最短有向路问题的实际问题例子
1.设备更新问题
(问题详见教材 
)
设备更新方案很多，如果用穷举法，情况繁杂，极费时间。通过建立网络模型可将原问题转化为网络的最短路问题来求解，就比较清晰。
所建立的网络模型如教材
所述，要理解图中弧及其权的含义。如图中的弧 
表示第 2 年年初购买一台设备并一直使用到第 5 年末，弧 
的权表示第 2 年年初购买一台设备的费用加上后面 4 年里的设备维修费，即 
。由此得到网络 
如教材 
图 10.4 所示。将 
到各点的最短路长度标在下图的顶点旁，最短路用蓝色标出，如下图。
|
|
 |
这样，制订一个最优的设备更新方案就等价于求
到 
的最短路。用 Dijkstra 算法即可求得最短路，然后根据所建立的网络模型，将所得的最短路还原成问题的解。
解决这个问题的关键是正确、灵活地建立网络模型，将实际问题转化为最短路问题的求解。如果在问题中还要考虑旧设备可作为二手货出售，则原模型的边和顶点不变，而将原来弧
的权减去第 
年初淘汰的旧设备的出售价，再用 Dijkstra 算法求解。