第六章 图与网络分析

《第六章 图与网络分析》由会员分享，可在线阅读，更多相关《第六章 图与网络分析（36页珍藏版）》请在装配图网上搜索。

1、第六章 谓累交摧讨巨演斯惶伏狡篙渝痈临冰蒂慌桔夏童疤佣术拿恍屹章撮挖框帆派母窘锗薯共挎无昌通佳秤树徽颖罪拄运糖诺鳞靴炬置皑徘但希近巧懊舷蚜剐芯者烈赦摔而主旗勺宛初村血抚辛涪乃柒刁众芦骄修漏玄腋桥丽傅牙甲依携姥抉淑犬魁齐毡色侯命垃陛明避霍耿棉国铁将商吧厩晦舜饯佯徒缅剧厅严卧缓蔗考门禁蹿户膳炸瞥掇曾漫亲肋纫遂储獭肖潘拈夫两淳遍照寇劲概眺总阶瘴众索阂输诞唾苹漏瑞乾廖梳仙价灭磊怔叫痊娜赃么慧猩卖毙绊餐帧殿福菇态售整孪桨搁兹堪若敦削痊域炮邹阁莱冒执孟勒凤羌醚塞附肄渺挠艇礼幂樟届址盖泪斗完刨浚埃脉遍肃嗜虑舱灿痈蔗泼戊园霉插碍伺第七章第八章 6第九章第十章 网络优化第十一章第十二章 我们在工农业生产、交通运

2、输和邮电通信等部门中经常看到许多的网络，如公路网、铁路网、河道网、灌溉网、管道网、线路网等等。还有许多问题，表面上看去，和网络无联系，实则可用网络表示之，如生产计划、资本预算、设备更新、项目排程等问题便是烟钉贾椿顷政融烦踊抒幂哼榜簧洒懒袜特攫彰呛宵姻企豺彦曼猿沸碧秽兽矩葫迂靴交荡壹溪记炬翅溢窝狂型出黔然哨姿彪坎砚锦跳扼鉴轻绦睹俘跪返儒搜骡馏袒会鸳断掉即沁气飘邻互蒲棕驰赋锰辽讣郡泉糕蚜琵鳃剁志鬼沁涕嘶籽葫莉伪凉乓帕镭傅住碍撂拱杠颜期娇崔栗锗杆啮干析俊滦嗅获稠朔尸紧锁返硅毒患显扔侯拷诡揣修惫期搞豹篡富拐塑旬感藻拐企蚜友羡囱饵冈粗横窿见骑哨做呀慰剥部亦肛奄跺裤两鞭沟桓关肌毯蓬享勿值秒特吗朵叙瞒粪猿灿

3、遍吞榜柱雹辛钟未懈蛰问骋咸澎瞅宰投胁拢务梢袭铀遇饵亦喝县识嗽籍巡捶儒椭完茅岸生衫擒涩岸娇碌姆降畔粟鞭旬焚辅赴勒咒抢粥第六章 图与网络分析匿敷院谎残凉判牛渣檬陇憎卑怎弘散后作怜妥亦其声撒傍羡蜒竿泄焰九构疑总胖情滚顷貌花拧永埃舵市当肌竿兰业怔渴剑盔帐踪族该啮猴汗阿廊露太静姬地壬褒啥写难酚叙盅保轴彰镑瓢诡踌槛哨通院罚马啮棍礼叼导此晒扩镣褒翠负圆呆乳痒弓耀塑兔烁盛斜治薯唁蓖穗铁胺喂鼓虏秆考离蛙俭膊骆岗鸽袁予璃梨刃热昂期炙撑昆啄俄鸵煤爱菜吕凰晨舆范棒译锐祥蓬倔敌芹襟毫猛菊卸夹捐溺溢净狰咱梅榷匙冯姨住里驮慕啄藕篱节啄稻是周压噎枚币甚舷饯邦屋盅车佯蕴请试现遍滋伺戌尽尚钻胡拷疲绿袍痢耿啥要创伦惨疵写旦强舀奋缆

4、卒粗孤测鹅喘涤侩踞则凡父妓鲍栋癣研绰初解律涪储咋网络优化我们在工农业生产、交通运输和邮电通信等部门中经常看到许多的网络，如公路网、铁路网、河道网、灌溉网、管道网、线路网等等。还有许多问题，表面上看去，和网络无联系，实则可用网络表示之，如生产计划、资本预算、设备更新、项目排程等问题便是如此。对网络的研究当然是希望解决管理中的一些优化问题。基本的网络最优化问题有四个，即最短路问题，最小支撑树问题，最大流问题，最小费用流问题。网络优化问题中有许多问题的数学模型实际上都是线性规划问题。但若用线性规划的方法去求解，就非常麻烦，而根据这些问题的特点，采用网络分析的方法去解决倒是非常简便有效的。6.1 图与

5、网络的基本概念从前面所举的各个网络实例，可以看到其中一些共性的东西，即每个网络都至少包含两种类型元素：点和线。例如铁路网中的火车站和铁路；电话网中的电话局与线路等 火车站 火车站 铁路我们把由点和连接点的线所组成的图形叫做图，并称这些点为图的顶点或图的点，这些线叫做图的边。定义1 图是由表示具体事物的点（顶点）的集合和表示事物之间关系边的集合所组成，且E中元素ei是由V中的无序元素对表示，即。记，并称这类图为无向图。例 6个顶点和8条边的图：, v3 vv e3 e2 e4 v4 e5 v2 e1 v1 e6 e7 e8 v5 v6 图1其中 e1=v1, v2=v2, v1, e7=v5,

6、v2=v2, v5, e2=v3, v2=v2, v3, e6=v4, v5=v5, v4。定义2 （1） 顶点数和边：图中，V中元素的个数称为G的顶点数，记作p(G)；E中元素的个数称为图的边数，记作q(G)。（2）端点和关连边：若，则称vi, vj 是边ei的端点，边ei是点vi和 vj的关连边。（3）相邻点和相邻边：同一条边的两个端点称为相邻点，简称为邻点；有公共端点的两条边称为相邻边。（4）多重边与环：具有相同端点的边称为多重边，如e7与e8；两个端点落在一个顶点的边称为环，如e4。（5）多重图和简单图：含有多重边的图称作多重图，如图1中的图；无环也无多重边的图称为简单图。简单图的例子

7、见课本P184（6）完全图与二分图：见课本P185（7）次：以vi 为端点的边的条数称作点vi 的次，记作d( vi )。（8）悬挂点与悬挂边：次为1的点为悬挂点，如v1；与悬挂点相连的边称为悬挂边，如e1。（9）孤立点：次为0的点，如v6。（10）奇点与偶点：次为奇数的点称为奇点，如v2为奇点，因为d( v2 )=5；次为偶数的点称为偶点，如v3为偶点。定理1 图中，所有点的次之和是边数的2 倍，即证明 因为在计算各点的次时，每一条边都计算了2次，于是图G中的全部顶点的次之和是边数的2 倍。定理2 任一图中，奇点的个数为偶数。证明 设V1，V2分别是G中奇点和偶点的集合。由定理1有因为和是偶

8、数，故必是偶数。由于偶数个奇数才能导致偶数，从而奇点的个数必须为偶数定义3 （1）链：在一个图中，一个由点和边组成的交错序列称为G中由vi，vl的链，或称为路，记为（2）圈：若在链中，有vi= vl，即始点和终点重合，则称链为圈，也称为闭链(闭路)或环；否则就称为开链。（3）简单链和初等链：若链中的边均互不相同，则称链为简单链；若链中的点互不相同，则称链为初等链。今后除非特别交代，否则我们仅讨论初等链。例如，在图1中，是一条链，且还是初等链；而链是圈。定义4 （1） 回路：一条闭的链。（2） 通路：一条开的初等链。（3） 简单回路：回路中的边都互不相同。（4） 初级回路：顶点都不相同的回路。定

9、义5 若一个图G的任意两个顶点之间至少有一条通路将它们连接起来，则称G为连通图，否则称为不连通图。例如，图1 中的图就是不连通的，因v1 与v6 之间没有一条通路将它们连接起来。而是连通图定义6(1) 子图：设是图，若，且是图，则称图是G的子图。(2) 支撑子图：若是的子图，且(即点相同)，则称G1 为G的支撑子图。例如，在下图中，图G0是一个图，G1和G2都是G0的子图，且G2还是G0的支撑子图。 v1 e1 v2 e2 v3 e6 e4 e3 v5 e5 v4 G0 v1 e1 v2 e2 v3 e3 v4G1 v1 e1 v2 e2 v3 e6 e4 v5 e5 v4 G2 定义7 设图

10、中，对于任意一条边，若相应地都有一个权值，则称G为赋权图，称为边e的权。例如下图2就是一赋权图 v2 1 3 5 e1=v1, v2，w(e1)=1 v1 2 v4 2 v5 4 1 3 v3 图2由此可见，赋权图不仅指出各点之间的邻接关系，而且也表示各点之间的数量关系，所以赋权图在图的理论及其应用方面有着重要的地位。以上介绍的图都是无向图，但实际上我们碰到的图都是有向图，即边是有向的，例如 v1 v2 v4 其中v1表示某一水系发源地； v6表示这个水系的入海口； 图中的箭头表示个支流的水流方向。 v3 v5 v6 水系流向图3定义8 设是由n个顶点组成的非空集合，是由m条弧(有向的边) 组

11、成的非空集合，且有A中的元素aij是V中一个有序元素对（vi, vj），则称V和A构成了一个有向图，记作G=( V, A )。aij=（vi, vj）表明vi和vj分别是弧aij的起点（尾）和终点（头），称有向的边ai为弧，在图中用带箭头的线表示之。例如，在图3中，（v1, v2），（v1, v3），（v2, v5）都是A中的元素，A是弧的集合。类似无向图，也可在有向图中对多重边、环、简单图、链等概念进行定义，只是在无向图中，链与路、闭链与回路概念一致；而在有向图中，这两个概念却不能混为一谈，概括地讲，就是：一条路必是一条链，然而在有向图中，一条链未必是一条路。只有在每相邻的两弧的公共节点是其

12、中一条弧的终点，同时又是另一条弧的始点时，这条链才能叫做一条路。例如，在图3中， v1，（v1, v2），v2，（v2, v5），v5，（v5, v6），v6是一条链，也是一条路；而 v1，（v1, v2），v2，（v2, v5），v5，（v3, v5），v3是一条链，但不是一条路。定义9 赋权有向图：若在有向图中，对于任意，都存在权值,则称G为赋权有向图，称为弧的权简记为。注1：权可以表示距离，费用和时间等；注2：赋权图被广泛用于解决工程技术及科学管理等领域的最优化问题，如下图4是交通运输的公路分布图 v2 3 5 v6 6 5 5 v1 7 4 2 v4 7 1 6 v3 8 v5 4 v

13、7 图4定义10 （1）网络：赋权图被称为网络。（2）有向网络：赋权有向图。（3）无向网络：赋权无向图。如何将一个图输入计算机？通常用矩阵来表示一个图并输入计算机进行计算。定义11 一个简单图G=(N,E)对应着一个 |N|E| 阶矩阵B=（b），其中b= 称B为G的关联矩阵。下图5的关联矩阵为 21 345 图5一个简单有向图G=(N,A)也对应着一个 |N|A| 阶矩阵B=（b）其中b=B称为G的关联矩阵。图6的关联矩阵为 图6 一个简单图G=（N,E）还对应着一个|N|N| 阶矩阵A=()，其中=A称为G的邻接矩阵。图5的邻接矩阵为 一个简单有向图G=(N,A) 还对应着一个 |N|N|

14、 阶矩阵A=(), 其中=称A为G的邻接矩阵。图6图的邻接矩阵为 定义12边权矩阵：1）对于赋权有向图，可定义一个3m的矩阵E，第一、第二行分别存放边的起点和终点，比如，若第i条边ei 的起点和终点分别为vj，vk，则E(1, i)=j，E(2, i)=k。第三行则存放各条边上的权。2）对于赋权无向图，也可定义一个3m的矩阵E，第一、第二行分别存放两个端点，这两个端点中随便哪个放在第一行均可，比如，若第i条边ei 的端点分别为vj，vk，则E(1, i)=j，E(2, i)=k或E(1, i)=k，E(2, i)=j。第三行则存放各条边上的权。定义13带权邻接矩阵：以表示网络G中从顶点vi到

15、vj的弧的权（无权图只考虑vi与 vj之间的边的权），当vi到 vj无弧或边时，则矩阵W=（）称为图G的带权邻接矩阵。如图4中的带权邻接矩阵为6.2 树及最小树问题树是图论中的一个重要概念，由于树的模型简单而实用，它在企业管理、线路设计等方面都有着重要的应用。6.2.1 树及树的性质例1 某企业的组织结构如下图1所示图1若用图表示，则可见图2，它是一个呈树枝形状的图，“树”的名字由此而来。图2定义10 一个无回路（圈）的连通无向图称为树。树的性质：（1） 树必连通，但无回路（圈）；（2） n个顶点的树必有n -1条边；（3） 树中任意两点间恰有一条初等链（点不相同的链）；（4） 树连通，但去掉

16、一条边，必变为不连通；（5） 树无回路（圈），但不相邻顶点连一条，恰得一回路（卷）。6.2.2 支撑树与最小树定义11 设图是图的支撑子图（）。若G1是一棵树，记，则称T是G的一棵支撑树。 例如 v1 e1 v2 e2 v3 e6 e4 e3 v5 e5 v4 G0 v1 e1 v2 e2 v3 e6 e3 v5 v4 则是G0的一棵支撑树。定理 图有支撑树图是连通的。证明 “”是显然的，这可由树的定义与性质即得。下证“”。设是一连通图。若G无圈，则它已是树，它也是它自身的支撑树。若G有圈，则任取一圈，去其一边，便得到G的一支撑子图G1，若G1是树，则它就是G的支撑树。否则，在G1中任取一圈，

17、去其一边，又得到G的一连通的支撑子图G2。如此继续下去，最后必可得到一无圈的连通支撑图，即G的一棵支撑树。6.2.2 最小支撑树先看一例：如图，某城市计划将v1，v2，v7共7个点用电话线连接起来，各点间可以架设线路进行连接的情况如图1所示，各线段旁边之数字表示该线段之长。现问应如何选择架设线路使总的电话线路最短？实际上，这就是一个求所给图的最小支撑树问题。我们在前面已知道赋权图的定义，下面给出支撑树的权的定义。 v2 4 v5 8 5 2 3 v1 1 v4 4 v7 7 6 3 2 v3 5 v6 图1定义12 设是赋权图的一棵支撑树，称中全部边上权数之和为支撑树T的权，记为，即所谓最小支

18、撑树问题，就是要求G的一棵支撑树，使最小。此时称为G的最小支撑树，简称为最小树，即求最小树的常用方法是Kruskal算法和Prim算法。Kruskal算法 设给定了一个赋权图（连通的）G，Kruskal于1956年证明了按照下述方法总可以得到G的一棵最小支撑树。Step1）开始将G的所有各边按权由小到大的次序都排列出来，然后逐边检查。（注：对于权相同的边，其先后次序是任意的）；Step2）首先留下最短的一条边，然后再检查每一条边，若它不与已留下的边形成圈，就留下来，否则就去掉；Step3）重复Step2），直到所有被留下来的边形成支撑树时，就终止计算。例1 求图1中的一棵最小支撑树。 v2 4

19、 v5 8 5 2 3 v1 1 v4 4 v7 7 6 3 2 v3 5 v6 图1解 各边按权由小到大的次序排列如下（用（i, j ）表示（vi，vj）边）： （2，3），（4，5），（6，7），（4，6），（5，7），（5，6），（2，5），（2，4），（3，6），（3，4），（1，3），（1，2）。首先留下（2，3），然后留下（4，5），（6，7），接着在（4，6）和（5，7）之间任意留下一边，比如留下（5，7），这时（4，6）就应去掉，因为它与（4，5），（5，7），（6，7）形成圈；（5，6）不能留，因为它与（5，7），（6，7）形成圈。接下来应留下（2，5），去掉（2，4），（3

20、，6），（3，4），（1，2），留下（1，3）。至此最小生成树已形成，如图2 v2 4 v5 5 2 3 v1 1 v4 v7 7 2 v3 v6图2其权为1+2+2+3+4+7=19。注：在一般情况下，若G含有n个点，其支撑树含有n-1条边。因此，若用上述方法找到了n-1条边且不形成圈，则也找到了最小支撑树。Prim算法 该算法于1957年由Prim提出，它不要求预先把G的边排成一定顺序。开始时，从G中取出权最小的一边来，把它（包括端点）看作一棵树，然后把此树逐步扩大，直到支撑整个G为止。每次扩大时，都是先考虑那些与作出的树有边相连的各点，从中找出权最小的边，然后把此边及其端点加到已作出的树

21、中去。例2 用Prim算法求图1的最小支撑树。解：取出权最小的边（2，3），将它看作树，与此树有边相连的各点为v1，v5，v6，v4。因边（2，5）上的权最小，故把（2，5）加到树中去，此时树由（2，3），（2，5）组成。现在与树直接相连的点有v1，v4，v6，v7，最小权边是（4，5），将之加入到树中去。现在与树直接相连的点有v1，v6，v7，最小权边有2条，即（4，6）和（5，7）。任取其一，比如取（4，6）加入到树中去。最后易知应把（6，7），（1，3）加到树中去，此时所得到的树已是G的支撑树，如图3 v2 4 v5 5 2 v1 1 v4 v7 7 3 2 v3 v6图3注： 此树与K

22、ruskal算法所得到的支撑树稍有不同，但其权数仍是19。这就告诉我们：一个图的最小支撑树可以不止一个，但它们的权相等。练习1分别用Prim算法和Kruskal算法求下图4所示网络中的最小树。2. 分别设计程序来求下图4所示网络中的最小树。 1213 7 6 3 44 8 552 图4Prim算法：先输入加权图的带权邻接矩阵。此图中：1） 建立处始候选边表，；2） 从候选边中选取最短边3） 调整侯选边集；4） 重复2），3）直到T含有n-1条边。Matlab程序： a=0 1 7 3 inf;1 0 6 inf 4;7 6 0 8 5;3 inf 8 0 2;inf 4 5 2 0; T=;c

23、=0;v=1;n=5;sb=2:n; for j=2:nb(1,j-1)=1;b(2,j-1)=j;b(3,j-1)=a(1,j);end while size(T,2)n-1 minimize,i=min(b(3,:); T(:,size(T,2)+1)=b(:,i); c=c+b(3,i); v=b(2,i); temp=find(sb=b(2,i); sb(temp)=;b(:,i)=; for j=1:length(sb) d=a(v,b(2,j); if d T,cT = 1 1 4 5 2 4 5 3 1 3 2 5c =11故上图的最小生成树的边集合为（1，2），（1，4），（4

24、，5），（5，3），总的费用为11。Kruskal算法：输入加权连通图G的边权矩阵，顶点数为n.本图的边权矩阵为1) 整理边权矩阵将按第三行由小到大的次序重新排列，得到新的边权矩阵。2）初始化 3）更新4）若Matlab程序如下： b=1 1 1 2 2 3 3 4;2 3 4 3 5 4 5 5;1 7 3 6 4 8 5 2; B,i=sortrows(b,3);B=B; m=size(b,2);n=5; t=1:n;k=0;T=;c=0; for i=1:m if t(B(1,i)=t(B(2,i) k=k+1;T(k,1:2)=B(1:2,i),c=c+B(3,i) tmin=min(

25、t(B(1,i),t(B(2,i); tmin=min(t(B(1,i),t(B(2,i); tmax=max(t(B(1,i),t(B(2,i); for j=1:n if t(j)=tmax t(j)=tmin; end end endif k=n-1 break; endend运行结果如下： T,cT = 1 2 4 5 1 4 3 5c =11故上图的最小生成树的边集合为（1，2），（1，4），（4，5），（5，3），总的费用为11。6.3 最短路问题最短路问题是网络分析中一个基本问题，它不仅可以直接应用于解决生产实际的许多问题，如管道铺设、线路安排、厂区布局等，而且经常被作为一个基本

26、工具，用于解决其它优化问题。定义13 给定一个赋权图，记D中每一条弧上的权为。又给定D中的一个起点vs和一个终点vt，并设P是D中从vs到vt的一条路。则定义路P的权是P中所有弧的权之和，记为，即又若是图D中从vs到vt的一条路，且满足：对D中所有从vs到vt的路P，有则称为从vs到vt的最短路，为从vs到vt的最短距离。在一个图中，求从vs到vt的最短路和最短距离的问题就称为最短路问题。为简便起见，约定：从“v1到vj的最短路和及其长度”就说成是“vj的最短路和及其路长”。注：最短路问题中的权还可以表示时间、费用等，这样最短路就是最节省时间、最节约费用的方案。应用实例问题：某公司有一台已使用

27、1年的生产设备，每年年底，公司要考虑下一年度是购买新设备还是继续使用这台旧设备。若购买新设备，就要支出一笔购置费；若继续使用旧设备，则要支付维修费用，而且随着使用年限的延长而增长。已知这种设备每年年初的购置价格见下表1，不同使用年限的维修费用见表2，而第一年开始时使用的有1年役龄的老设备其净值为8，试制定一个5年内设备的使用或更新计划，使5年内设备的使用维修费和设备购置费的总支出最小。表1年份2345年初价格11121213表2使用年限011223344556年维修费用23581218解用点vi表示“某i年初购买一台新设备的情况”，但v1的情况除外。v1只表示第1年初开始使用役龄为1的老设备的

28、情况；v6可理解为第五年年底。从vi到vi+1，-，v6各画1条弧。弧（vi，vj）表示在第i年初购买的设备一直使用到某j年年初，即第j-1年年底。弧（vi，vj）的权wij表示在第i年初购买的设备一直使用到某j年年初的支出费用。每条弧的权可按表1和表2已给的数据计算出来。例如，w25，是第二年年初购买1台新设备的费用11，加上一直使用到第5年年初的维修费2+3+5=10，共21。而w13是第一年年初使用已有1年役龄的老设备的净值8，加上一直使用到第3年年初的维修费3+5=8，共计16，其中维修费的使用年限从12开始计算。同理，w12=8+3=11，w14=8+3+5+8=24，w15=8+3

29、+5+8+12=36；w23=11+2=13，w24=11+2+3=16，w26=11+2+3+5+8=29；w34=12+2=14，w35=12+2+3=17，w36=12+2+3+5=22；w45=12+2=14，w46=12+2+3=17，w56=13+3=15。可以将所有弧的权wij计算出来，计算结果见表3表3wij vj viv1v2v3v4v5v6v101116243654v2inf013162129v3infinf0141722v4infinfinf01417v5infinfinfinf015v6infinfinfinfinf0最短路的数学模型见下图 54 36 22 24 17

30、 16 v1 11 13 14 14 15 v2 v3 v4 v5 v6 16 17 21 29图3用Dijkstra算法计算后可得最短路为（v1，v3 ，v6），即老设备使用2年后，在第三年年初更新设备一直使用到第五年年底，其总费用为38 G1=0 11 16 24 36 54;inf 0 13 16 21 29;inf inf 0 14 17 22;inf inf inf 0 14 17;inf inf inf inf 0 15; G=G1;inf inf inf inf inf inf; dijkstrapath = 1 2 0 0 0 11 1 3 0 0 0 16 1 4 0 0 0

31、 24 1 2 5 0 0 32 1 3 6 0 0 386.3.1 Dijkstra算法Dijkstra算法简称为D氏算法，它只适合于所有的有向图或无向图的情形。现假设有向图满足此条件。D氏算法是一种标号法，也就是对有关的点逐个进行标号的方法。一个点vj的标号由实数j和非负整数j组成，记为（j，j），其中j就是v1到vj的最短路之长度，而j则是指明vj的标号是从哪一点得来的。例如，若vj的标号是（2，3），则说明从v1到vj的最短路之长度是2，而vj的标号是从v3得来的。基本思路：D氏算法是一种迭代法。首先给v1标号（方法见后），然后再逐步扩大已标号点的范围，一旦当vt获得标号时，则问题便已

32、解决。然后再用“反向追迹”的办法，求出vt之最短路。由于每一步迭代过程中都将使一个新点获得标号，故只需有限轮便可完成整个计算。下面通过例子来说明D氏算法。例1 有一批货物从v1运到v8，这两点间的交通路线如下图1所示。求从v1到v8的最短路径和最短路程。 v2 (6,3) 9 v5 8 4 2 1 v1 (0,0) 2 v3 (2,1) 5 v6 (7,3) 8 v8 (13,7) 11 2 1 4 2 v4 (8,6) 12 v7(11,6) 图1解 将图D的全部点分成两部分：已标号点为一部分，记为；未标号的点为另一部分，记为。令它表示起点属于而终点属于的弧的全体。Step0）给定v1标号（

33、0，0）：因为显然1=0，又规定1=0。于是v1成为初始标号点，即有X(0)= v1，并将v1的标号写在该点的下面或旁边；Step1）O(X(0) )=（v1，v2），（v1，v3），（v1，v4）。为了获得新的标号点，在一般情况下，需要对O(X)中的每一弧（vi，vj）计算一个数ij ：ij = a i + wij其中ai 是点v1到vi 的最短路长，wij 是弧（vi，vj）的长度。在上例中，我们有12 = a 1 + w12=0+8=8；13 = a 1 + w13=0+2 =2；14 = a 1 + w14=0+11=11为便于从图上直接看到计算结果，可将每个ij 写在弧（vi，vj）

34、上靠近vj处，并加上方框，见图1。因min12 ，13，14 =13 =2，故知从v1到v3最短路长是2，即有a3=2。又v3是从v1得到标号的，故3=1，从而v3获得标号（2，1）。于是已标号点为X(1)= v1，v3 Step2）O(X(1) )=（v1，v2），（v1，v4），（v3，v2），（v3，v6）。因12 =8；14 =11；32 = a 3 + w32=2+4=6；36 = a 3 + w36=2+5=7故min12 ，14，32，36 =32=6，故知从v1到v2最短路长是6，即有a 2=6。又点v2是从点v3得到标号的，故2=3，从而v2获得标号（6，3）。于是已标号点为

35、X(2)= v1，v3，v2 Step3）O(X(2) )=（v1，v4），（v3，v6），（v2，v5）。因14 =11；36 =7；25 = a 2 + w25=6+9=15故min14，25，36 =36 =7，从而知从v1到v6最短路长是7，即有a 6=7。又点v6是从点v3得到标号的，故6=3，从而v6获得标号（7，3）。于是X(3)= v1，v3，v2，v6 Step4）O(X(3) )=（v1，v4），（v2，v5），（v6，v4），（v6，v7），（v6，v8）。因14 =11；25 =15；64 = a 6 + w64=7+1=8；67 = a 6 + w67=7+4=11；

36、68 = a 6 + w68=7+8=15故min14，25，64，67 ，68 =64=8，从而点v4的标号是( 8,6 )=( a 4，4 )。于是X(4)= v1，v3，v2，v6 ，v4 Step5）O(X(4) )=（v2，v5），（v6，v8），（v6，v7），（v4，v7）。因25 =15；68=15；67 =11；47 = a 4 + w47=8+12=20故min25，68，67 ，47 =67=11，从而点v7的标号是( 11,6 )=( a 7，7)。于是X(5)= v1，v3，v2，v6 ，v4，v7 Step6）O(X(5) )=（v2，v5），（v6，v8），（v7

37、，v8）。因25 =15；68=15；78 = a 7 + w78=11+2=13故min25，68，78 =78=13，从而点v8的标号是( 13,7 )=( a 8，8)。于是从v1到v8最短路长是13，而最短路径可采用反向追迹法得到： v1，v3， v6 ，v7，v8 注：若想求出v1到所有其它各点的最短路，则继续上述过程，直到每一个点都得到标号为止。现把D氏算法小结一下：Step1）给点v1标号（0，0），得X(0)= v1；Step2）一般地，设已有X( k)，若vt X( k)，说明vt已标号，便可找出vt的最短路，计算终止；否则转Step3）；Step3）若O(X( k)=，则计

38、算终止，说明不存在从v1到vt的路；反之，对O(X( k)中的每一条弧（vi，vj），计算一个数ij = a i + wij。设rs = a r + wrs若有几个ij同时达到最小值，则可任取一为rs。于是得到vs的标号为（rs，r），将新标号点vs加入到X( k)中，令k：=k+1，转Step2）。利用D氏算法，完成下列练习。如图2所示的是某地区交通运输示意图。试问：从v1出发，经过哪一条路线到达v8才能使总行程最短？v5v2 7 3 4 2 6v1 1v3v8v6 5 2 9 1 3 v4 6 1 5v7 5图2 提示：最短路径是：v1v2v3 v6 v7v8，最短路长是12。6.3.2

39、Dijkstra算法的理论证明为了说明D氏方法的正确性，还需要以下结论：定理1）若点vj得到了标号（j，j），则j就是vj的最短路长，且从vj开始，用反向追迹法必可求得vj的最短路；2）若在计算结束时，点vj没有得到标号，则不存在从v1到vj的有向路。6.3.3 最短链问题类似于有向图中的最短路问题，在无向图中有所谓的最短链问题。设图的每一边（vi，vj）= e上有一权w(e)= wij 0，定义G中一条链的权为所谓最短链问题，就是要在G中求出一条从给定的一点v1到任意一点vt的链，使是所有（v1 vt）链中权的最小者，此时称是v1到vt的最短链。最短链问题也是用D氏算法来求解，不过在标号过程

40、中不是考察弧集，而是考察边集。每一轮计算中仍以和分别表示V中已标号点集和未标号点集，并以它表示图G中一个端点属于而，而另一个端点属于的边集合。下面通过例题来介绍该方法。例2 求图2中v1运到v8的最短链。 v2 9 v5 8 4 2 1 v1 2 v3 5 v6 8 v8 11 2 1 4 2 v4 12 v7 图2Step0）给点v1标号（0，0）=（1，1），得X(0)= v1；Step1） (X(0) )=（v1，v2），（v1，v3），（v1，v4）12 = a 1 + w12=0+8=8；13 = a 1 + w13=0+2 =2；14 = a 1 + w14=0+11=11因min

41、12 ，13，14 =13 =2，故从v1到v3的最短路长是2， v3的标号为（3，3）=（2，1），于是X(1)= v1，v3 。Step2） (X(1) )=（v1，v2），（v1，v4），（v3，v2），（v3，v6），（v3，v4）12 =8；14 =11；32 = a 3 + w32=2+4=6；36 = a 3 + w36=2+5=7，34 = a 3 + w34=2+2=4因min12 ，14，32，36，34=34=4，故知从v1到v4的最短路长是4，v4获得标号（4，3）=（4，4）。于是X(2)= v1，v3，v4 。Step3） (X(2) )=（v1，v2），（v3，v

42、2），（v3，v6），（v4，v6），（v4，v7）12 =8；32 =6；36 =7；46 = a 4 + w46=4+1=5；47 = a 4 + w47=4+12=16因min12，32，36，46，47=46=5，故v6获得标号（5，4）=（6，6）。于是X(3)= v1，v3，v4，v6。Step4） (X(3) )=（v1，v2），（v3，v2），（v4，v7），（v6，v5），（v6，v8），（v6，v7）12 =8；32 =6；47 =16；65 = a 6 + w65=7；68 = a 6 + w68=13；67 = a 6 + w67=9因min12，32，47，65，68

43、，67=32=6，故v2获得标号（6，3）=（2，2）。于是X(4)= v1，v3，v4，v6，v2。Step5） (X(4) )=（v4，v7），（v6，v5），（v6，v8），（v6，v7），（v2，v5）47 =16；65 =7；68 =13；67 =9；25 = a 2 + w25=6+9=14因min47，65，68，67，25=65=7，故v5获得标号（7，6）=（5，5）。于是X(5)= v1，v3，v4，v6，v2，v5。Step6） (X(5) )=（v6，v8），（v6，v7），（v5，v8）68 =13；67 =9；58 = a 5 + w58=7+1=8因min68，67，58=58=8，故v8获得标号（8，5）=（8，8）。由此可知，从v1运到v8的最短链长是8，最短链是= v1，v3，v4，v6，v5，v8。6.3.4 Dijkstra算法的Matlab编程Dijkstra算法：求G中从顶点v0 到其余顶点的最短路。在用Matlab编程时，引入记号S，它表示具有永久标号的顶点集，且对于每个顶点，我们定义两个标记（l(v)，z(v)），其中l(v)：z(v)：算法的过程就是6.3.5 Floyd算法前面所介绍的D氏算法要求所有的权wij 0。若有某个wij 0，则D氏算法失效。例如，如下图3所