§2最短路问题 例2电信公司准备在甲、乙两地沿路架设一条光缆线,问如何架 设使其光缆线路最短?下图给出了甲乙两地间的交通图。权数表示两 地间公路的长度(单位:公里)。 7(乙地) 6 V (甲地) 3 3 解:这是一个求无向图的最短路的问题。可以把无向图的每一边 (v;v1)都用方向相反的两条弧(vv;)和(vv;)代替,就化为有向 图,即可用 Dijkstra算法来求解。也可直接在无向图中用 Dijkstra算法 来求解。只要在算法中把从已标号的点到未标号的点的弧的集合改成 已标号的点到未标号的点的边的集合即可。 运筹
管 理 运 筹 学 11 §2 最短路问题 例2 电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架 设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两 地间公路的长度（单位：公里）。 解：这是一个求无向图的最短路的问题。可以把无向图的每一边 （vi ,vj）都用方向相反的两条弧（vi ,vj）和（vj ,vi）代替，就化为有向 图，即可用Dijkstra算法来求解。也可直接在无向图中用Dijkstra算法 来求解。只要在算法中把从已标号的点到未标号的点的弧的集合改成 已标号的点到未标号的点的边的集合即可。 V1 （甲地） 15 17 6 2 4 4 3 10 6 5 v2 V7 （乙地） v3 v4 v5 v6
§2最短路问题 例2最终解得: 最短路径v1→V3→v5→V6v,每点的标号见下图 V7(乙地) (13,3) (0.s) 3 (18,5) 5) (甲地)10 43) 管理蓦 12
管 理 运 筹 学 12 §2 最短路问题 例2最终解得： 最短路径v1 v3 v5 v6 v7，每点的标号见下图 （0,s） V1 （甲地） 15 17 6 2 4 4 3 10 6 5 (13,3) v2 (22,6) V7 （乙地） V5 (14,3) V6 (16,5) V3 (10,1) V4 (18,5)
§2最短路问题 例3设备更新问题。某公司使用一台设备,在每年年初,公司就 要决定是购买新的设备还是继续使用旧设备。如果购置新设备,就要 支付一定的购置费,当然新设备的维修费用就低。如果继续使用旧设 备,可以省去购置费,但维修费用就高了。请设计一个五年之内的更 新设备的计划,使得五年内购置费用和维修费用总的支付费用最小。 已知:设备每年年初的价格表 年份 2 3 5 年初价格 12 12 13 设备维修费如下表 使用年数0 1-2 2-3 3-4 4-5 每年维修 8 18 费用 运筹 13
管 理 运 筹 学 13 §2 最短路问题 例3 设备更新问题。某公司使用一台设备，在每年年初，公司就 要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要 支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设 备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更 新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。 已知：设备每年年初的价格表 设备维修费如下表 年份 1 2 3 4 5 年初价格 11 11 12 12 13 使用年数 0-1 1-2 2-3 3-4 4-5 每年维修 费用 5 6 8 11 18
§2最短路问题 例3的解 将问题转化为最短路问题,如下图: 用v表示“第年年初购进一台新设备”,弧(vv1)表示第许年初购进 的设备一直使用到第j年年初 把所有弧的权数计算如下表 16 30 41 59 2 16 22 30 41 3 17 23 31 4 17 23 6
管 理 运 筹 学 14 §2 最短路问题 例3的解： 将问题转化为最短路问题，如下图： 用vi表示“第i年年初购进一台新设备”,弧（vi ,vj）表示第i年年初购进 的设备一直使用到第j年年初。 把所有弧的权数计算如下表： v1 v2 v3 v4 v5 v6 1 2 3 4 5 6 1 16 22 30 41 59 2 16 22 30 41 3 17 23 31 4 17 23 5 18 6
§2最短路问题 (继上页)把权数赋到图中,再用 Dijkstra算法求最短路。 59 2 30 2 16 16 1718 6 22 23 31 最终得到下图,可知,v1到v的距离是53,最短路径有两条: →3→v6和v→Ⅴ→v 30,1) (0,s) 1 16 17 (41,1 18 (16,1 2,D 23 31 (53,3) (53,4) 15
管 理 运 筹 学 15 §2 最短路问题 (继上页) 把权数赋到图中，再用Dijkstra算法求最短路。 最终得到下图，可知，v1到v6的距离是53，最短路径有两条： v1 v3 v6和 v1 v4 v6 v1 v2 v3 v4 v5 v6 16 22 30 41 59 16 22 30 41 31 23 17 17 18 23 V1 （0,s） v3 v4 (41,1) v5 v6 22 30 41 59 16 (22,1) 30 41 31 23 17 17 18 23 V2 （16,1） 16 (30,1) (53,3) (53,4)