1、图与网络分析图与网络分析(Graph Theory and Network Analysis)图与网络的基本知识图与网络的基本知识最短路问题最短路问题 树及最小树问题树及最小树问题最大流问题最大流问题最小费用最大流问题最小费用最大流问题BDACABCD哥尼斯堡哥尼斯堡“七桥七桥”难难题题一笔画问题一笔画问题 一、一、图与网络的基本知识图与网络的基本知识（一）、（一）、图与网络的基本概念图与网络的基本概念 EADCBv1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10图图1,(,),u vVu vEu v两两个个点点属属于于如如果果边边属属于于，则则称称两两点点相相邻邻.,)u v
2、u v称称为为边边(的的端端点点jVvV 一一个个图图是是由由点点集集和和 中中元元素素的的无无序序对对的的一一个个集集合合,(,),kjEeGV EVv构构成成的的二二元元组组 记记为为其其中中 中中的的元元素素,kVGEeE叫叫做做顶顶点点表表示示图图 的的顶顶点点集集合合,中中的的元元素素 叫叫做做边边表表示示.G图图 的的边边集集合合 123456,Vv v v v v v 例例 12345678910,Ee e e e e e e e e e 112212323,ev vev vev v 434513635,ev vev vev v 735856966,ev vev vev v 10
3、16,evv,.V EG当当为为有有限限集集合合时时称称为为有有限限图图否否则则为为无无限限图图()|,()|m GEGn GVG用用表表示示图图 中中的的边边数数表表示示图图 的的顶顶点点.个个数数v4v6v1v2v3v5图图2(,),(,),ijijv vEv v对对于于任任一一条条边边属属于于如如果果边边端端点点无无序序 则则它它是是,.G无无向向边边 此此时时图图 称称为为无无向向图图(,),ijijv vvv如如果果边边端端点点有有序序 则则它它表表示示以以 为为始始点点为为终终点点的的,.G有有向向边边(或或称称为为弧弧)此此时时图图 称称为为有有向向图图 123456,Vv v
4、v v v v 13212325(,),(,),(,),(,),Ev vv vv vv v 35455456(,),(,),(,),(,)v vv vv vv v,ijije eEue e两两条条边边属属于于如如果果它它们们有有一一个个公公共共端端点点则则称称相相邻邻.,.ije eu边边称称为为 的的关关联联边边4.4.一条边的两个端点如果相同一条边的两个端点如果相同,称此边为环。称此边为环。6.6.不含环和多重边的图称为简单图，含有多重边的不含环和多重边的图称为简单图，含有多重边的图称为多重图。图称为多重图。8.8.有向完全图则是指任意两个顶点之间有且仅有一条有向完全图则是指任意两个顶点之
5、间有且仅有一条有向边的简单图。有向边的简单图。7.7.每一对顶点间都有边相连的无向简单图称为完全图。每一对顶点间都有边相连的无向简单图称为完全图。,deg(),()vvvd v10.10.以以点点 为为端端点点的的边边数数叫叫做做点点 的的次次 记记作作简简记记为为9.(,),GV EVX Y图图的的点点集集可可以以分分为为两两个个非非空空子子集集即即,XYV XYE使使得得 中中每每条条边边的的两两个个端端点点必必有有一一个个,(),XYG端端点点属属于于另另一一个个端端点点属属于于则则称称 为为二二部部图图 偶偶图图(,)GX Y E有有时时记记作作1v3v5v2v4v6v1v2v3v4v
6、1v2v3v4v 次为零的点称为弧立点，次为次为零的点称为弧立点，次为1 1的点称为悬挂点。连结的点称为悬挂点。连结悬挂点的边称为悬挂边。次为奇数的点称为奇点，次为偶悬挂点的边称为悬挂边。次为奇数的点称为奇点，次为偶数的点称为偶点。数的点称为偶点。任何图中，次为奇数的顶点必为偶数个。任何图中，次为奇数的顶点必为偶数个。有向图中有向图中,所有顶点的入次之和等于所有顶点的出次之和所有顶点的入次之和等于所有顶点的出次之和定理定理1 1 任何图中，顶点次数的总和等于边数的任何图中，顶点次数的总和等于边数的2 2倍。倍。,(),iiivvdv 有有向向图图中中以以 为为始始点点的的边边数数称称为为点点
7、的的出出次次 用用表表示示,(),iiivvdv 以以 为为终终点点的的边边数数称称为为点点 的的入入次次 用用表表示示.iv点点的的出出次次与与入入次次之之和和就就是是该该点点的的次次,由由于于每每条条边边必必与与两两个个顶顶点点关关联联 在在计计算算点点的的次次时时 每每条条边边2,.均均被被计计算算了了两两次次 所所以以顶顶点点次次数数的的总总和和等等于于边边数数的的 倍倍1212(),VVGVVV 设设和和分分别别为为图图 中中奇奇点点和和偶偶点点的的集集合合由由1212()()()v Vv Vv Vd vd vd vm定定理理 知知22,(),.v Vmd v 由由于于为为偶偶数数
8、而而是是若若干干个个偶偶数数之之和和 也也是是偶偶数数11(),|.v Vd vV 所所以以必必为为偶偶数数 即即是是偶偶数数v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10e11(a)e5e7v1v2v5v6v7e1e6e8(b)子图子图v1v2v3v4v5v6v7e1e6e7e9e10e11(c)支撑子图支撑子图(,),GV EEEVVE 图图若若是是 的的子子集集是是 的的子子集集 且且中中的的边边仅仅,(,).VGVEG 与与中中的的顶顶点点相相关关联联 则则称称是是 的的一一个个子子图图,().VVGG 特特别别地地 若若则则称称为为 的的生生成成子子图图 支支
9、撑撑子子图图(,),GV EG无无向向图图若若图图 中中某某些些点点与与边边的的交交替替序序列列可可以以排排成成0112111(,.,),(,)(,.,)kkktttiiiiiiiiiive v evevevvtk的的形形式式 且且0kiivvk则则称称这这个个点点边边序序列列为为连连接接与与的的一一条条链链，链链长长为为点点边边列列中中没没有有重重复复的的点点和和重重复复边边者者为为初初等等链链。00,kkiiiiGvvvv无无向向图图 中中，连连结结与与的的一一条条链链 当当与与是是同同一一个个点点时时称称此此链链为为圈圈.圈圈中中既既无无重重复复点点也也无无重重复复边边者者为为初初等等圈
10、圈.,(,)(,),GV EDV A在在实实际际应应用用中中 给给定定一一个个图图或或有有向向图图1,(),Vv在在 中中指指定定两两个个点点 一一个个称称为为始始点点 或或发发点点 记记作作一一个个称称为为(),.nv终终点点 或或收收点点 记记作作其其余余的的点点称称为为中中间间点点 对对每每一一条条弧弧(,),.ijijv vAw 对对应应一一个个数数称称为为弧弧上上的的 权权通通常常把把这这种种.赋赋权权的的图图称称为为网网络络e3v1v2v3v4v5v6e7e8e1e2e4e5e6e9e10()().当当链链 圈圈 上上的的边边方方向向相相同同时时，称称为为道道路路 回回路路v4v6
11、v1v2v3v511635546,Sv e v e v e v图图4 4中中，为为一一条条道道路路.2495104,Sv e v ev 为为一一个个回回路路.11233547584423,Sv e v e v e v e v e v e v图图 中中1112335475,Sv e v e v e v e v223354758442,Sv e v e v e v e v e v31123321,Sv e v e v e v(二二)、图图的的矩矩阵阵表表示示()(,),(,),ijijGV Ev vw 网网络络 赋赋权权图图其其边边有有权权构构造造矩矩阵阵(),:ijn nAa 其其中中0(,)i
12、jijijwv vEa 其其他他.AG称称矩矩阵阵 为为网网络络 的的权权矩矩阵阵(,),|,(),:ijn nGV EVnAa 对对于于图图构构造造一一个个矩矩阵阵其其中中10(,)ijijv vEa 其其他他.AG则则称称矩矩阵阵 为为图图 的的邻邻接接矩矩阵阵654321654321 010101101001010111101010001101111010vvvvvvvvvvvvB 例例权矩阵为：权矩阵为：邻接矩阵为：邻接矩阵为：v5v1v2v3v4v64332256437654321654321 030303302004020576305020007204346040vvvvvvvvv
13、vvvA 二、二、树及最小树问题树及最小树问题 已知有六个城市，它们之间要架设电话线，要求任意已知有六个城市，它们之间要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短。两个城市均可以互相通话，并且电话线的总长度最短。v1v2v3v4v5v6(,),.TV EVn Em 则则关关于于树树的的下下列列说说法法是是等等价价的的1().T是是一一个个树树21(),.Tmn无无圈圈 且且31(),.Tmn连连通通 且且4(),T无无圈圈 但但每每加加一一新新边边即即得得唯唯一一一一个个圈圈.5(),.T连连通通 但但任任舍舍去去一一边边就就不不连连通通6(),.T中中任任意意两两点点
14、 有有唯唯一一链链相相连连1 1、连通且不含圈的无向图称为树。、连通且不含圈的无向图称为树。树中次为树中次为1 1的点称为树叶，次大于的点称为树叶，次大于1 1的点称为分支点。的点称为分支点。12()()证证明明,.TTT由由于于 是是树树 由由定定义义知知 是是连连通通的的并并且且无无圈圈只只需需证证明明 中中的的1mmn边边数数等等于于顶顶点点个个数数减减1 1，即即2.,nT 用用归归纳纳法法当当时时 由由于于 是是树树 所所以以两两点点间间显显然然有有且且仅仅有有1,mn一一条条边边 满满足足112,nkkTk归归纳纳假假设设时时命命题题成成立立 即即有有个个顶顶点点时时 有有.,nk
15、Tk 条条边边 当当时时 因因为为 连连通通无无圈圈个个顶顶点点中中至至少少有有一一个个点点次次1.,(,).uuuv u为为 设设此此点点为为即即 为为悬悬挂挂点点 设设连连结结 点点的的悬悬挂挂边边为为(,),Tv uuTT T从从 中中去去掉掉边边及及 点点不不会会影影响响 的的连连通通性性 得得图图为为树树12,(,)kkv uu只只有有个个顶顶点点 所所以以有有条条边边 再再把把，加加上上去去,可可知知1.Tkk 当当 有有 个个顶顶点点时时有有条条边边23()().T只只需需证证明明 是是连连通通图图2.,(),Tlli 反反证证法法 设设 不不连连通通 可可以以分分为为 个个连连
16、通通分分图图设设第第 个个11,.,liiiinnnin 子子图图有有 个个顶顶点点因因为为第第 个个分分图图是是树树 所所以以有有,l条条边边 个个分分图图共共有有边边数数为为111()liinnln .T与与已已知知矛矛盾盾 所所以以 为为连连通通图图34()(),.,TCCT若若 中中有有圈圈 设设为为可可以以去去掉掉 中中一一条条边边 并并不不影影响响 的的连连通通性性,.如如果果剩剩余余图图中中仍仍有有圈圈 可可如如前前那那样样继继续续拿拿去去一一条条边边1(),ppT 像像这这样样去去掉掉 条条边边后后得得到到一一个个没没有有圈圈的的连连通通图图1.,TnpTT 显显然然有有条条边
17、边 但但既既然然是是树树 顶顶点点个个数数又又与与 相相同同1.nTnT 为为 个个,所所以以中中应应有有条条边边 矛矛盾盾即即 中中无无圈圈,Tu vT设设 中中两两点点间间无无边边直直接接相相连连 由由于于 是是连连通通图图 所所以以经经由由,u v其其他他点点必必有有一一条条链链连连结结，且且此此链链是是连连结结这这两两点点的的唯唯一一链链(),(,),.TTu v 否否则则 中中出出现现圈圈 则则后后 出出现现唯唯一一一一个个圈圈45()().,TTu v先先证证 连连通通 若若 不不是是连连通通图图由由定定义义至至少少存存在在两两点点之之间间.(,),u v无无路路可可通通 那那么么
18、加加上上一一边边也也不不会会形形成成圈圈 与与已已知知矛矛盾盾.(,),(,)Tu vu v再再证证每每舍舍去去一一边边便便不不连连通通 若若 中中有有一一边边舍舍去去后后(,),(,)Tu vTTu v 图图仍仍然然连连通通 那那么么由由于于无无圈圈是是一一棵棵树树4(,),()Tu vT 但但加加一一边边后后就就是是 仍仍无无圈圈 与与中中树树每每加加一一新新边边必必.出出现现唯唯一一圈圈相相矛矛盾盾5661()(),()(),.均均显显然然 故故定定理理证证毕毕一个图一个图G 有生成树的充要条件是有生成树的充要条件是G 是连通图。是连通图。v1v2v3v4v5v1v2v3v4v5G若若图
19、图 的的生生成成子子图图是是一一棵棵树树，则则称称该该树树为为G G的的生生成成树树(支支撑撑树树).证证 必必要要性性是是显显然然的的:.G充充分分性性 设设 是是连连通通图图1(),GGG如如果果 不不含含圈圈 则则 本本身身就就是是一一棵棵树树 从从而而 是是它它自自身身的的.生生成成树树2(),GG如如果果 含含圈圈 任任取取一一圈圈 从从圈圈中中任任意意去去掉掉一一条条边边 得得到到图图111,GGGG的的一一个个生生成成子子图图如如果果不不含含圈圈,那那么么是是 的的一一棵棵生生成成11;,GG树树 如如果果仍仍含含圈圈 那那么么从从中中任任取取一一个个圈圈 从从圈圈中中再再任任意
20、意去去掉掉2,GG一一条条边边 得得到到图图 的的一一个个生生成成子子图图如如此此重重复复 最最终终可可以以得得,kkGGGG到到 的的一一个个生生成成子子图图它它不不含含圈圈 则则是是图图 的的一一棵棵生生成成树树.用破圈法求出下图的一个生成树。用破圈法求出下图的一个生成树。v1v2v3v4v5e1e2e3e4e5e6e7e8v1v2v3v4v5e2e4e6e8v1v2v3v4v5e1e2e3e4e5e6e7e8（一）（一）破圈法破圈法（二）（二）避圈法避圈法112,eee在在图图中中任任取取一一条条边边找找出出一一条条不不与与 构构成成圈圈的的边边再再找找出出12312,.,.,ke ee
21、e ee不不与与构构成成圈圈的的边边一一般般地地 设设已已有有找找出出121,.,kke eee 一一条条不不与与构构成成圈圈的的边边重重复复这这个个过过程程 直直到到.,不不能能进进行行下下去去为为止止 这这时时 由由所所有有取取出出的的边边所所构构成成的的图图是是.G图图 的的一一棵棵支支撑撑树树v1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v5 某六个城市之间的道路网如下图所示，要求沿着已知长某六个城市之间的道路网如下图所示，要求沿着已知长度的道路联结六个城市的电话线网，使电话线的总长度最度的道路联结六个城市的电话线网，使电话线的总长
22、度最短。短。v1v2v3v4v5v66515723445v1v2v3v4v5v6123443.3.最最小小生生成成树树问问题题11(,),TV EGE 如如果果图图是是图图 的的一一个个生生成成树树 那那么么称称上上所所有有边边*,().TS TGT的的权权的的和和为为生生成成树树 的的权权 记记作作如如果果图图 的的生生成成树树*(),S TGT的的权权在在 的的所所有有生生成成树树 中中的的权权最最小小 即即*()min()TS TS T*.TG那那么么称称是是 的的最最小小生生成成树树v1v2v3v4v514231352v1v2v3v4v514231352v1v2v3v4v5142313
23、52v1v2v3v4v514231352,sjiPDvvvP若若 是是 中中从从 到到 的的最最短短路路是是 中中的的一一个个点点.,sisivPvvv那那么么,从从 沿沿 到到 的的路路是是从从 到到 的的最最短短路路 事事实实上上 若若这这个个:(,),GV E 最最短短路路的的一一般般提提法法为为 设设为为连连通通图图 图图中中各各边边(,)(,),ijijijijstv vllv vv v 有有权权表表示示之之间间没没有有边边为为图图中中任任意意.:stvv 两两点点,求求一一条条路路,使使它它为为从从 到到 的的所所有有路路中中总总权权最最短短即即(,)()ijijv vLl 最最小
24、小.,sisQvvPvQ结结论论不不成成立立 设设 是是从从 到到 的的最最短短路路，令令是是从从 沿沿 到到达达,jsjvPPPvv的的路路,那那么么,的的权权就就比比 的的权权小小 这这与与 是是从从 到到 的的最最短短路路矛矛盾盾。(,),jjjl其其中中是是正正整整数数 它它表表示示获获得得此此标标号号的的前前一一点点的的下下标标,sDijkstrav算算法法是是一一种种标标号号法法 它它的的基基本本思思路路是是从从起起点点 出出发发,jv逐逐步步向向外外探探寻寻最最短短路路 执执行行过过程程中中 给给每每一一个个顶顶点点 标标号号(,jsjlvv或或表表示示从从起起点点 到到该该点点
25、 的的最最短短路路的的权权 称称为为固固定定标标号号 记记为为)(sjPvv标标号号 或或表表示示从从起起点点 到到该该点点 的的最最短短路路的的权权的的上上界界 称称为为,).T临临时时标标号号 记记为为 标标号号TT方方法法的的每每一一步步是是去去修修改改 标标号号,并并且且把把某某一一个个具具有有 标标号号,PDP的的点点改改变变为为具具有有 标标号号的的点点 从从而而使使 中中具具有有 标标号号的的顶顶点点1,stpvv 数数多多一一个个 这这样样至至多多经经过过步步 就就可可以以求求出出从从 到到 及及各各点点.j 的的最最短短路路 再再根根据据每每个个点点标标号号的的第第一一个个数
26、数反反向向追追踪踪找找出出.最最短短路路径径,iP TPTSi用用分分别别表表示示某某个个顶顶点点的的 标标号号标标号号表表示示在在第第 步步时时PKP已已具具有有 标标号号点点的的集集合合,表表示示刚刚获获得得 标标号号点点的的下下标标(,)DijkstraDV A方方法法的的具具体体步步骤骤：给给定定赋赋权权有有向向图图0000(),(),(),ssssiSvP vvvv开开始始令令对对每每一一个个(),jT vsks 令令，令令1(),();ijijjSVvS LP v若若，算算法法终终止止,此此时时,对对每每个个否否则则转转下下一一步步2(),(,)kkjjivPv vAvS设设 为为
27、刚刚获获得得 标标号号的的点点 考考察察每每个个使使且且,()()min(),()jjjjkkjvT vT vT vP vw的的点点将将修修改改为为()(),()(),jkkjjkkjjT vP vwT vP vw若若则则把把修修改改为为把把修修改改;.k为为否否则则不不修修改改3()()min()jijijvST vT v令令(),()()jijijijiT vvTPP vT v若若则则把把的的 标标号号变变为为 标标号号 即即令令 111,(),.iijiiSSvkjii令令把把 换换成成，返返回回否否则则终终止止,()();jijjjivSl vP vvS此此时时对对每每一一个个有有而而
28、对对每每一一个个，有有()()jjl vT v.iSiP其其中中表表示示在在第第 步步时时已已具具有有 标标号号的的点点的的集集合合01110100,(),()jisSvP vT v 解解：开开始始时时令令12 38,(,.,)jj1110 01,(,),(,),kvv即即给给起起点点 标标给给其其余余点点标标这这时时 为为刚刚获获得得P标标号号的的点点，其其余余均均为为T T标标号号的的点点.123412202,(,),vv v vv vA vSv考考察察与与 相相邻邻的的点点因因故故把把 的的临临时时22112033()min(),()min,T vT vP vw标标号号修修改改为为21,
29、此此时时同同理理得得330551()min,T v440661()min,T v.其其余余点点的的标标号号不不变变10 0(,)v21 3(,)v31 5(,)v41 6(,)v2233(),(),TT vP v在在所所有有的的 标标号号中中，最最小小的的为为于于是是令令102122,SSvv vk1:i 22563,vPvv v v这这时时 为为刚刚获获得得 标标号号的的点点，考考察察与与 相相邻邻的的点点25515(,),v vA vSv因因故故把把 的的临临时时标标号号修修改改为为55225537102()min(),()min,T vT vP vw663472()min,T v同同理理
30、335 3 142()min,T v21 3(,)v52 10(,)v62 7(,)v32 4(,)v34(),P v于于是是令令34(),TT v在在所所有有的的 标标号号中中，最最小小的的为为2131233,SSvv v vk2:i 3346,vPvv v这这时时 为为刚刚获获得得 标标号号的的点点，考考察察与与 相相邻邻的的点点34424(,),v vA vSv因因故故把把 的的临临时时标标号号修修改改为为4433446 4 153()min(),()min,T vT vP vw667 4263()min,T v同同理理45(),P v于于是是令令45(),TT v在在所所有有的的 标标
31、号号中中，最最小小的的为为32412344,SSvv v v vk3:i 4467,vPvv v这这时时 为为刚刚获获得得 标标号号的的点点，考考察察与与 相相邻邻的的点点32 4(,)v63 6(,)v43 5(,)v46636(,),v vA vSv因因故故把把 的的临临时时标标号号修修改改为为6644666 536()min(),()min,T vT vP vwv此此时时 的的临临时时63,标标号号不不修修改改 故故7755104()min,T v同同理理66(),TT v在在所所有有的的 标标号号中中，最最小小的的为为66(),P v于于是是令令436123466,SSvv v v v
32、 vk43 5(,)v63 6(,)v74 10(,)v4:i 66578,vPvv v v这这时时 为为刚刚获获得得 标标号号的的点点，考考察察与与 相相邻邻的的点点65545(,),v vA vSv因因故故把把 的的临临时时标标号号修修改改为为55665510 6286()min(),()min,T vT vP vw7710 6 176()min,T v同同理理77(),TT v在在所所有有的的 标标号号中中，最最小小的的为为5471234677,SSvv v v v v vk8869156()min,T v77(),P v于于是是令令63 6(,)v86 15(,)v76 7(,)v56
33、 8(,)v778vPvv这这时时 为为刚刚获获得得 标标号号的的点点，考考察察与与 相相邻邻的的点点78848(,),v vA vSv因因故故把把 的的临临时时标标号号修修改改为为88778815 75127()min(),()min,T vT vP vw58(),TT v在在所所有有的的 标标号号中中，最最小小的的为为65512345675,SSvv v v v v v vk58(),P v于于是是令令76 7(,)v87 12(,)v5:i 558vPvv这这时时 为为刚刚获获得得 标标号号的的点点，考考察察与与 相相邻邻的的点点6:i 58868(,),v vA vSv因因故故把把 的
34、的临临时时标标号号修修改改为为88778815 75127()min(),()min,T vT vP vw,最最后后只只剩剩下下一一个个临临时时标标号号点点 故故令令888127()(),P vT v18121.vv至至此此已已找找到到从从起起点点 到到终终点点 的的最最短短距距离离为为再再根根据据第第 个个,j标标号号反反向向追追踪踪 求求出出最最短短路路径径为为123678vvvvvv1v事事实实上上，按按这这个个算算法法，也也找找出出了了从从起起点点 到到各各个个中中间间点点的的.,最最短短路路径径和和最最短短距距离离 例例如如12365158.vvvvvvv即即从从 到到 的的最最短短
35、路路径径，距距离离为为例例2、用Dijkstra算法求下图从v1到v6的最短路。v1v2v3v4v6v5352242421 解解 （1）首先给v1以P标号，给其余所有点T标号。0)(1vP)6,3,2()(ivTi（2）（3）330,min)(,)(min)(12122lvPvTvT550,min)(,)(min)(13133lvPvTvT3)(2vP（4）4 13,5min)(,)(min)(23233lvPvTvT523,min)(,)(min)(24244lvPvTvT523,min)(,)(min)(25255lvPvTvTv1v2v3v4v6v53522424214)(3vP（5）（
36、6）844,6min)(,)(min)(35355lvPvTvT5)(4vP5)(5vP945,min)(,)(min)(46466lvPvTvT725,min)(,)(min)(56566lvPvTvT7)(6vP（7）（8）（9）（10）反向追踪得v1到v6的最短路为：6521vvvv237184566134105275934682求从求从1到到8的最短路径的最短路径237184566134105275934682X=1,w1=0min c12,c14,c16=min 0+2,0+1,0+3=min 2,1,3=1X=1,4,p4=1p4=1p1=023718456613410527593
37、4682X=1,4min c12,c16,c42,c47=min 0+2,0+3,1+10,1+2=min 2,3,11,3=2X=1,2,4,p2=2p1=0p4=1p2=2237184566134105275934682X=1,2,4min c13,c23,c25,c47=min 0+3,2+6,2+5,1+2=min 3,8,7,3=3X=1,2,4,6,p6=3p2=2p4=1p1=0p6=3237184566134105275934682X=1,2,4,6min c23,c25,c47,c67=min 2+6,2+5,1+2,3+4=min 8,7,3,7=3X=1,2,4,6,7,
38、p7=3p2=2p4=1p1=0p6=3p7=3237184566134105275934682X=1,2,4,6,7min c23,c25,c75,c78=min 2+6,2+5,3+3,3+8=min 8,7,6,11=6X=1,2,4,5,6,7,p5=6p2=2p4=1p1=0p6=3p7=3p5=6237184566134105275934682X=1,2,4,6,7min c23,c53,c58,c78=min 2+6,6+9,6+4,3+8=min 8,15,10,11=8X=1,2,3,4,5,6,7,p3=8p2=2p4=1p1=0p6=3p7=3p5=6p3=8237184
39、566134105275934682X=1,2,3,4,6,7min c38,c58,c78=min 8+6,6+4,3+7=min 14,10,11=10X=1,2,3,4,5,6,7,8,p8=10p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10237184566134105275934682X=1,2,3,4,6,7,81到8的最短路径为1，4，7，5，8，长度为10。p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10求从求从V V1 1 到到 V V8 8 的最短路线。的最短路线。3 3 V V 1 1 V V 2 2 V V V V 4 4 V V
40、5 5 V V V V 6 6 7 7 V V 8 8 3 3 7 7 2 2 1 1 2 2 3 3 3 3 4 4 1 1 2 2 2 2 6 6 ,本本算算法法在在给给某某个个点点标标号号时时 也也可可以以通通过过找找该该点点的的各各个个来来源源点点.的的方方法法实实现现0 000,(,),(),sssvl v 开开始始时时 给给起起点点 标标即即,jjvv一一般般地地 在在给给点点 标标号号时时 要要找找出出与与 有有弧弧关关联联且且箭箭头头指指向向12(),.,jjiiimjvvvvvv的的各各点点 称称为为 的的来来源源点点 不不妨妨设设是是 的的来来源源点点1212(),(),.
41、,(),(,),(,),.,(,)iiimml vl vl vw ij w ijw ij其其标标号号为为为为弧弧12(,),(,),.,(,),(,(),ijijimjjkjvvvvvvvv l v的的权权值值 则则给给点点 标标以以其其中中1122()min()(,),()(,),.,()(,)jiijiijimimjl vl vw vvl vw vvl vw vv()(,)kkjl vw v v1,jbellmanvv根根据据最最优优化化原原理理 由由始始点点 到到 的的最最短短路路径径必必是是由由11(,)kkjkjvvv vvvv到到某某个个 的的最最短短路路径径再再加加上上弧弧的的权
42、权值值,是是 到到1,()jjjvl vvv最最短短路路径径上上的的点点 且且是是 的的来来源源点点 显显然然是是 到到 最最短短1 2,(,(),.,kjv l vjn 路路径径的的长长度度 所所以以给给每每个个顶顶点点以以标标号号.即即可可获获得得最最短短路路径径线线路路和和长长度度的的信信息息1,v给给始始点点 标标号号 第第一一个个标标号号表表示示的的是是来来源源点点 第第二二个个标标号号表表示示11100(),(),l vvl v 由由于于 是是始始点点 故故令令始始点点的的第第一一个个标标号号为为 令令10 0(,).v于于是是得得到到始始点点 的的标标号号为为212,()vvl
43、v的的来来源源点点是是且且可可计计算算得得到到2112033()min()(,)min,l vl vw v v213(,).vv得得到到 的的标标号号312,vv v的的来来源源点点有有计计算算3113223()min()(,),()(,)l vl vw v vl vw v v05 3 14min,324(,).vv得得到到 的的标标号号为为413,vv v的的来来源源点点有有计计算算4114334()min()(,),()(,)l vl vw v vl vw v v06 415min,415(,).vv于于是是得得到到 的的标标号号为为52666234,vv vvvv v v的的来来源源点点
44、有有但但 还还未未标标号号 而而 的的来来源源点点均均已已标标号号，故故可可计计算算6226336446()min()(,),()(,),()(,)l vl vw v vl vw v vl vw v v35 42 536min,636(,),vv因因而而得得到到 的的标标号号计计算算5225665()min()(,),()(,)l vl vw v vl vw v v37 628min,568(,).vv故故 的的标标号号为为746,vv v的的来来源源点点有有计计算算7447667()min()(,),()(,)l vl vw v vl vw v v55 617min,767(,).vv得得到
45、到 的的标标号号8567,vv v v终终点点 的的来来源源点点有有,计计算算8558668778()min()(,),()(,),()(,)l vl vw v vl vw v vl vw v v86 69 7512min,8712(,).vv终终点点 的的标标号号为为标标号号过过程程结结束束,沿沿着着第第一一个个标标号号 由由终终点点反反向向跟跟踪踪 易易得得最最短短路路径径为为123678vvvvvv8.v而而终终点点 的的第第二二个个标标号号就就是是此此最最短短路路的的长长度度V1V2V3V4V5V6V7V8 P=0T=+T=+T=+T=+T=+T=+T=+P=T=3T=+T=7T=+T
46、=+T=+T=+T=6T=7P=T=5T=+T=+T=+P=T=6T=6 T=8T=+T=+P=T=6 T=8T=9T=12 P=T=8T=10T=10 P=T=9T=11再无其它再无其它T 标号，所以标号，所以 T(V8)=P(V8)=10;min L()=10P=T=10 由此看到，此方法不仅求出了从由此看到，此方法不仅求出了从V1 到到 V8 的最短路的最短路长，同时也求出了从长，同时也求出了从V1 到到 任意一点任意一点 的最短路长。将从的最短路长。将从V1 到到 任一点的最短路权标在图上，即可求出从任一点的最短路权标在图上，即可求出从V1 到到 任一点的最短路线。本例中任一点的最短路
47、线。本例中V1 到到 V8 的最短路线是：的最短路线是：v1 v2 v5 v6 v8 1v2v3v4v5v9v8v7v6v6231216410362342101v3v2v5v8v（二）、（二）、逐次逼近法逐次逼近法算法的基本思路与步骤：首先设任一点vi到任一点vj都有一条弧。显然，从v1到vj的最短路是从v1出发，沿着这条路到某个点vi再沿弧(vi,vj)到vj。则v1到vi的这条路必然也是v1到vi的所有路中的最短路。设P1j表示从v1到vj的最短路长，P1i表示从v1到vi的最短路长，则有下列方程：开始时，令 即用v1到vj的直接距离做初始解。从第二步起，使用递推公式：求 ，当进行到第t步
48、，若出现则停止计算，即为v1到各点的最短路长。min11jiiijlPP),2,1(1)1(1njlPjj）（nklPPjikiikj,3,2min)1(1)(1)(1kjP）（njPPtjtj,2,1)1(1)(1）（njPtj,2,1)(1例例2、18v1v2v3v4v52635135211211v6v7v837求图中求图中v v1 1到到各点的最短路各点的最短路 18v1v2v3v4v52635135211211v6v7v837（0，0）（v3，-5）（v1，-2）（v3，-7）（v2，-3）（v4，-5）（v3，-1）（v6，6）例例3 3、求：、求：5 5年内，哪些年初购置新设备，使
49、年内，哪些年初购置新设备，使5 5年内的总费用最年内的总费用最小。小。解：（解：（1 1）分析：可行的购置方案（更新计划）是很多的，）分析：可行的购置方案（更新计划）是很多的，如：如：1 1）每年购置一台新的，则对应的费用为：每年购置一台新的，则对应的费用为：11+11+12+12+13+5+5+5+5+5=84 2)2)第一年购置新的，一直用到第五年年底，则总费第一年购置新的，一直用到第五年年底，则总费用为：用为：11+5+6+8+11+18=59 显然不同的方案对应不同的费用。显然不同的方案对应不同的费用。第第i i年度年度 1 2 3 4 5购置费购置费 11 11 12 12 13设备
50、役龄设备役龄0-1 1-2 2-3 3-4 4-5维修费用维修费用 5 6 8 11 18 （2 2）方法：将此问题用一个赋权有向图来描述，然后求）方法：将此问题用一个赋权有向图来描述，然后求这个赋权有向图的最短路。这个赋权有向图的最短路。求解步骤：求解步骤：1 1）画赋权有向图：）画赋权有向图：设设 V Vi i 表示第表示第i i年初，年初，(V(Vi i,V,Vj j)表示第表示第i i 年初购买新年初购买新设备用到第设备用到第j j年初（年初（j-1j-1年底），而年底），而W Wi ji j 表示相应费用，表示相应费用，则则5 5年的一个更新计划相当于从年的一个更新计划相当于从V V
