第八章 图与网络分析
也叫网络规划。我们讲三个问题：最短路问题，最大流问题，最小费用最大流问题。
第一讲： 最短路问题（与上章设备更新凑成一讲）
最短路问题是网络理论中应用最广泛的问题之一。许多优化问题都可以使用这个模型，如设备更新、管道的铺设、线路的安排、厂区的布局等。
最短路问题的一般提法是：设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）划成