§1 图与网络的基本概念 §2 树图与最小生成树 §3 最短路问题 §4 最大流问题 §5 最小费用最大流问题 第7章 图与网络模型 §1 图与网络的基本概念 §2 树图与最小生成树 §3 最短路问题 §4 最大流问题 §5 最小费用最大流问题

§3 最短路问题 最短路问题是对一个赋权的有向图G（权数可能是路程的长度、花费的成本等等）中的指定的两个点Vs和Vt找到一条从Vs到Vt的路，使得这条路上所有弧的权数的总和最小，这条路被称为从Vs到Vt的最短路，这条路上所有弧的权数的总和被称之为从Vs到Vt的距离。

3.1 求解最短路的Dijkstra算法（Dijkstra algorithm, 1959） Dijkstra算法也称为双标号算法。所谓双标号，也就是对图中的点vj赋予两个标号(lj,kj)，第一个标号lj表示从起点vs到vj的最短路的长度，第二个标号kj表示在vs到vj的最短路上vj前面一个邻点的下标。 给起点v1以标号(0,s)表示从v1到v1的距离为0，v1为起点。 找出已标号的点的集合I，没标号的点的集合J以及弧的集合{(vi,vj)|vi∈I,vj∈J}，这里这个弧的集合是指所有从已标号的点到未标号的点的弧的集合。 如果上述弧的集合是空集，则计算结束。如果vt已标号(lt,kt)，则vs到vt的距离即为lt，而从vs到vt的最短路径，则可以从kt反向追踪到起点vs而得到。如果vt未标号，则可以断言不存在从vs到vt的有向路。否则转下一步。 对上述弧的集合中的每一条弧，计算sij=li+cij在所有的sij中，找到其值为最小的弧，不妨设此弧为(vc,vd)，则给此弧的终点以双标号(scd,c),返回第2步。

例1. 求下图中v1到v6的最短路。 v2 7 3 2 v6 v4 5 v1 5 1 1 3 2 v5 5 v3

给起始点v1标以(0,s)，表示从v1到v1的距离为0。 已标号点集I={v1}，未标号点集J={v2,v3,v4,v5,v6}，弧集{(vi,vj)|vi∈I,vj∈J}={(v1,v2),(v1,v3),(v1,v4)}，并有s12=l1+c12=0+3=3,s13=l1+c13=0+2=2,s14=l1+c14=0+5,min(s12,s13,s14)=s13=2. 我们给弧(v1,v3)的终点v3标以(2,1). I={v1,v3},J={v2,v4,v5,v6},弧集{(vi,vj)|vi∈I,vj∈J}={(v1,v2),(v1,v4),(v3,v4)}且s34=l3+c34=2+1=3,min(s12,s14,s34)=s12=s34=3.给弧(v1,v2)的终点标以(3,1),弧(v3,v4)的终点标以(3,3). I={v1,v2,v3,v4},J={v5,v6},弧集{(vi,vj)|vi∈I,vj∈J}={(v2,v6),(v4,v6)},并有s26=l2+c26=3+7=10,s46=l4+c46=3+5=8,min(s26,s46)=s46=8. I={v1,v2,v3,v4,v6},J={v5},弧集为∅，计算结束。v5没有标号表明从v1到v5没有有向路。 最短路径为v1￫v3￫v4￫v6.

例1的各点的标号如下(v1到v5没有有向路） (3,1) v2 7 (8,4) 3 2 v6 (3,3) v4 5 v1 5 1 (0,s) (2,1)

3.2 最短路问题的应用 例2.电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给了甲、乙两地间的交通图，图中的点v1,v2,...,v7表示7个地点，其中v1表示甲地，v7表示乙地，点之间的联线（边）表示两地之间的公路，边所赋的权数表示两地间的公路长度。 17 v7 乙地 v2 v4 15 6 5 6 3 v6 4 v1 甲地 2 v5 10 4 v3

起始点v1标号为(0,s). I={v1},J={v2,v3,v4,v5,v6,v7},边集{[vi,vj]|vi,vj中一个∈I,另一个∈J}={[v1,v2],[v1,v3]}，且s12=l1+c12=0+15=15，s13=l1+c13=0+10=10，min(s12,s13)=s13=10，边[v1,v3]中未标号点v3标以(10,1). I={v1,v3},J={v2,v4,v5,v6,v7},边集{[vi,vj]}={[v1,v2],[v3,v2],[v3,v5]},且s32=l3+c32=10+3=13，s35=l3+c35=10+4=14，min(s12,s32,s35)=s32=13.边[v3,v2]中未标号的点v2标以(13,3). I={v1,v3,v2},J={v4,v5,v6,v7},边集{[vi,vj]}={[v3,v5],[v2,v4],[v2,v7]},且s24=l2+c24=13+6=19,s27=l2+c27=13+17=30,min(s35,s24,s27)=s35=14.边[v3,v5]中未标号的点v5标以(14,3). I={v1,v2,v3,v5},J={v4,v6,v7},边集{[vi,vj]}={[v2,v4],[v5,v4],[v2,v7],[v5,v6]},并有s54=l5+c54=14+4=18,s56=l5+c56=14+2=16,min(s24,s54,s27,s56)=s56=16.边[v5,v6]中未标号的点v6标以(16,5).

I={v1,v2,v3,v5,v6},J={v4,v7}.边集{[vi,vj]}={[v2,v4],[v2,v7],[v5,v4],[v6,v7]},且s67=l6+c67=16+6=22,min(s24,s27,s54,s67)=s54=18.边[v5,v4]中未标号的点v4标以(18,5). I={v1,v2,v3,v4,v5,v6},J={v7}.边集{[vi,vj]}={[v2,v7],[v4,v7],[v6,v7]},且s47=l4+c47=18+8=23,min(s27,s47,s67)=s67=22.边[v6,v7]中未标号的点v7标以(22,6). 此时I={v1,v2,v3,v4,v5,v6,v7},J=∅.边集合{[vi,vj]}为空集，计算结束。 从v1到v7的最短距离为22,其最短路径为v1￫v3￫v5￫v6￫v7.

例2的各点标号如下： (22,6) (13,3) 17 v7 乙地 v2 (18,5) 15 6 5 6 v4 3 v6 4 v1 甲地 2 (16,5) (0,s) v5 10 4 v3 (14,3) (10,1)

例3.设备更新问题。某公司试用一台设备，在每年年初，公司就要决定是购买新设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。现在需要我们制定一个五年之内的更新设备计划，使得五年内购置费和维修总的支付费用最小。这种设备每年年初的价格以及使用不同时间的设备所需要的维修费如下表所示。 年份 1 2 3 4 5 年初价格 11 12 13 使用年数 0-1 1-2 2-3 3-4 4-5 每年维修费用 5 6 8 11 18

将该问题转化成求最短路问题，vi表示“第i年年初购进一台新设备”，对于弧(vi,vj)，它的权数定义为从第i年年初购进设备使用到第j-1年年底所花费的购置费及维修费的总和，计算结果如下： 2 3 4 5 6 — 16 22 30 41 59 17 23 31 18

59 41 31 30 23 22 16 v3 17 v4 16 17 v5 18 v6 v1 v2 22 23 30 41

起始点v1标以(0,s). I={v1},J={v2,v3,v4,v5,v6}.弧集{(vi,vj)|vi∈I,vj∈J}={(v1,v2),(v1,v3),(v1,v4),(v1,v5),(v1,v6)}并有s12=l1+c12=0+16=16,s13=l1+c13=0+22=22,s14=l1+c14=0+30=30,s15=l1+c15=0+41=41,s16=l1+c16=0+59=59,min(s12,s13,s14,s15,s16)=s12=16.给弧(v1,v2)的终点v2标以(16,1). I={v1,v2},J={v3,v4,v5,v6}.弧集{(vi,vj)|vi∈I,vj∈J}={(v1,v3),(v1,v4),(v1,v5),(v1,v6),(v2,v3),(v2,v4),(v2,v5),(v2,v6)}并有s23=l2+c23=16+16=32,s24=l2+c24=16+22=38,s25=l2+c25=16+30=46,s26=l2+c26=16+41=57,min(s13,s14,s15,s16,s23,s24,s25,s26)=s13=22.给弧(v1,v3)的终点v3标以(22,1).

I={v1,v2,v3},J={v4,v5,v6}.弧集{(vi,vj)|vi∈I,vj∈J}={(v1,v4),(v1,v5),(v1,v6),(v2,v4),(v2,v5),(v2,v6),(v3,v4),(v3,v5),(v3,v6)}并有s34=l3+c34=22+17=39,s35=l3+c35=22+23=45,s36=l3+c36=22+31=53, min(s14,s15,s16,s24,s25,s26,s34,s35,s36)=s14=30.给弧(v1,v4)的终点v4标以(30,1). I={v1,v2,v3,v4},J={v5,v6}.弧集{(vi,vj)|vi∈I,vj∈J}={(v1,v5),(v1,v6),(v2,v5),(v2,v6),(v3,v5),(v3,v6),(v4,v5),(v4,v6)}并有s45=l4+c45=30+17=47,s46=l4+c46=30+23=53, min(s15,s16,s25,s26,s35,s36,s45,s46)=s15=41.给弧(v1,v5)的终点v5标以(41,1). I={v1,v2,v3,v4,v5},J={v6}.弧集{(vi,vj)|vi∈I,vj∈J}={(v1,v6),(v2,v6),(v3,v6),(v4,v6),(v5,v6)}并有s56=l5+c56=41+18=59, min(s16,s26,s36,s46,s56)=s36=s46=53.给弧(v3,v6)和(v4,v6)的终点v6标以(53,3)和(53,4).

59 41 31 30 23 22 (22,1) 16 v3 17 v4 16 17 v5 18 v6 v1 v2 (30,1) (41,1) (53,3) 22 (0,s) (16,1) 23 (53,4) 30 41