第八章 图与网络分析
也叫网络规划。我们讲三个问题：最短路问题，最大流问题，最小费用最大流问题。
第一讲： 最短路问题（与上章设备更新凑成一讲）
最短路问题是网络理论中应用最广泛的问题之一。许多优化问题都可以使用这个模型，如设备更新、管道的铺设、线路的安排、厂区的布局等。
最短路问题的一般提法是：设G?(V,E)为连通图，图中各边(vi,vj)有权lij（lij=∞表示vi，vj之间没有边），vs，vt为图中任意两点，求一条道路?，使它是从vs到vt的所有路中总权最小的路。即：L(?)=
(vi,vj)??l?。
ij最短路算法中1959年由Dijkstra（狄克斯特洛）提出的算法被公认为是目前最好的方法，我们称之为Dijkstra算法。下面通过例子来说明此法的基本思想。
条件：所有的权数lij≥0。 思路：逐步探寻。
v2（4） 5 4 4 v1（0） 4 6 v3（6） 7 下求v1到v8的最短路：
1） 从v1出发，向v8走。首先，v1到v1的距离为0，给v1标号（0）。画第一个圈。（表
明已标号，或已走出v1）
2） 从v1出发，只有两条路可走，（v1，v2），（v1，v3），其距离记为k11，k12。当然
想选一条长度短的路，即 Min｛（k12）,k13｝=｛4,6｝=4
给v2标号（4）：表明走出v1后走向v8的最短路目前看是v2，最优距离是4。
1给（v，v）划成粗线。 ○12v4（9） 9 7 5 v6（13） 4 v8（15）
1 6 v5（8） v7（14） 1
2划第二个圈。 ○
现已完成第二个圈内的路已考察完毕，或者说，已走出包含v1，v2的第二个圈。 3）出了第二个圈，接着往下走，有三条路可走：（v1，v3），（v2，v4），（v2，v5）。那条路最近？记三条路长度为k13，k24，k25，即求：
Min｛（k13）,k24,k25｝=min｛6,9,8｝=6
给v3标号（6）：表明从第二个圈出来最近的一站是v3，总长度是6。
○1给（v1，v3）划成粗线。 ○
2划第三个圈。 表明：圈内的点已完成考察。
4）现已走出第三个圈，向v8奔。有四条路可走，最优路线在何方？即： Min｛k24,（k25）,k34,k35｝=min｛9,8,10,13｝=8
给v5标号（8）：表明从第三个圈出来后最近的一站是v5，总长度是8。
○1给（v2，v5）划成粗线。 ○
2划第四个圈。 表明：圈内的点已完成考察。
5）现已走出第四个圈，向v8奔。有四条路可走，最优路线在何方？即： Min｛k56,k57,（k24）,k34｝=min｛13,14,9,10｝=9
给v4标号（9）：表明从第四个圈出来后最近的一站是v4，总长度是9。
○1给（v2，v4）划成粗线。 ○
2划第五个圈。 表明：圈内的点已完成考察。
6）现已走出第五个圈，向v8奔。有四条路可走，最优路线在何方？即： Min｛k46,k47,（k56）,k57｝=min｛18,16,13,14｝=13
给v6标号（13）：表明从第五个圈出来后最近的一站是v6，总长度是13。
○1给（v5，v6）划成粗线。 ○
2划第六个圈。 2
表明：圈内的点已完成考察。
7）现已走出第六个圈，向v8奔。有三条路可走，最优路线在何方？即： Min｛k68,k47,（k57）｝=min｛17,16,14｝=14
给v7标号（14）：表明从第六个圈出来后最近的一站是v7，总长度是14。
1给（v，v）划成粗线。 ○572划第七个圈。 ○
表明：圈内的点已完成考察。
8）最后，奔v8，有两条路，考察最短路： Min｛k68,(k78)｝=min｛17,15｝=15 给v8标号（15），同时给（v7，v8）划粗线。 最后，从v8逆寻粗线到v1，得最短路：
v1—v2—v5—v7—v8 长度为15。
第二讲：最短路问题的两个应用
最短路问题在图论应用中处于很重要的地位，下面举两个实际应用的例子。 例12/P-164 设备更新问题
某工厂使用一台设备，每年年初工厂要作出决定：继续使用，购买新的？如果继续使用旧的，要负维修费；若要购买一套新的，要负购买费。试确定一个5年计划，使总支出最小。
若已知设备在各年的购买费，及不同机器役龄时的残值与维修费，如表8-2所示 表8-2 项目 购买费 维修费 残值 第1年 第2年 第3年 第4年 第5年 11 5 4 12 1-2 6 3 13 2-3 8 2 14 3-4 11 1 14 4-5 18 0 机器役龄 0-1 解：把这个问题化为最短路问题。
用点vi表示第i年初购进一台新设备，虚设一个点v6，表示第5年底。 边（vi，vj）表示第i年购进的设备一直使用到第j年初（即第j-1年底）。
边（vi，vj）上的数字表示第i年初购进设备，一直使用到第j年初所需支付的购买费、维修的全部费用（可由表8-2计算得到）。例如：（v1，v4）边上的28是第一年初的购买费
3
11加上三年的维修费5，6，8，减去3年役龄机器的残值2；（v2，v4）边上的20是第二年初购买费12减去机器残值3与使用二年维修费5，6之和，见下图：
59 40 28 30 19 21 13 14 v 15 15 1（0） 12 v2（12） v3（1920 ） v4（28） v5（40） v6（49） 29 22 41 这样设备更新问题就变为：求从v1到v6的最短路问题， 1）v1（0）。
2）min｛(k12),k13,k14,k15,k16｝=12, 给v2标号（12），（v1，v2）加粗线。 3）min｛(k13),k14,k15,k16, k23,k24, k25,k26｝
=｛19, ? 13+12, ? ｝=19,
给v3标号（19），（v1，v3）加粗线。
4) min{(k14),k15,k16,k24,k25,k26,k34,k35,k36｝
=｛59,? 19+30,? 12+20,?｝=28, 给v4标号（28），（v1，v4）加粗线。 5) min｛(k15),k16,k25,k26,(k35),k36,k45,k46｝
=｛40,? 41, 40,? 43, ?｝=40, 对应两个边： 给v5标号（40），（v1，v5）加粗线,（v3，v5）加粗线。 6）min｛k16,k26,(k36),k46,k56｝= min｛59,53,49,50,55｝=49 给v6标号（49），（v3，v6）加粗线。
计算结果：v1—v3—v6为最短路，路长为49。
即：在第一年、第三年初各购买一台新设备为最优决策。这时5年的总费用为49。
4