图与网络分析

第八章 图与网络分析

也叫网络规划。我们讲三个问题:最短路问题,最大流问题,最小费用最大流问题。

第一讲: 最短路问题(与上章设备更新凑成一讲)

最短路问题是网络理论中应用最广泛的问题之一。许多优化问题都可以使用这个模型,如设备更新、管道的铺设、线路的安排、厂区的布局等。

最短路问题的一般提法是:设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)划成

>>展开全文<<
12@gma联系客服:779662525#qq.com(#替换为@)