第7章图论与网络分析-第3

《第7章图论与网络分析-第3》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、最短路定义：设图G=（V，E）为连通图，图中各边（vi,vj）有权lij，vs,vt为图中任意两点，求一条通路u，使它是从vs到vt的所有路中总权最小的路。即：第3节最短路问题109631702115132861722291511914397463109631702115132861722291511914397463一、最短路问题的标号算法算法步骤：（1）给起点vs以P标号P(vs)=0，其余各点均给T标号T(vi)=+∞（2）若vi点为刚得到P标号的点，考虑这样的点vj：(vi,vj)属于E，且vj为T标号。对vj的T标号进行如下修改：T(vj)=min[T(vj),p(vi)+

2、lij]（3）比较所有具有T标号的点，把最小者改为P标号，即：P(vi)=min[T(vi)]同时存在两个以上最小者时，可同时改为P标号。（4）若图中全部点均为P标号则停止。否则用vi代vj转回（2）。从一点到任意点的最短路例2：木器厂有六个车间，办事员经常要到各个车间了解生产进度。从办公室到各车间的路线由图1给出。找出点1（办公室）到其它各点（车间）的最短路5127563425527313571权wij(dij)距离、价格点（vi）边eij或记为（vi，vj）Dinkstra标号法这是解决网络中某一点到其它点的最短路问题时目前认为的最好方法。在这个问题中我们讨论的是从网络中的点1到

3、其它各点的最短路。0从点1出发，因L11=0，在点1处标记5127563425527313571005127563425527313571从已标号的点出发，找与这些相邻点最小权数（距离）者，找到之后：标号；边变红。2051275634255273135712从已标号的点出发，找与这些相邻点最小权数（距离）者，找到之后：标号；边变红。30512756342552731357123重复上述步骤，直至全部的点都标完。40512756342552731357123后续过程请同学们自行完成。4051275634255273135712347813小结①从点1出发，因L(1,1)=0，在点1处标

4、记②从点1出发，找相邻点r使得边L(1,r)权数（距离）最小，若L(1,r)=L(1,1)+d(1,r)将标于点r处。并将边1r变红。0L(1,r)③从已标号的点出发，找与这些相邻点最小权数（距离）者，若L(1,p)=Min{L(1,r)+d(r,p)}，这里r为已标号者下标，p为未标号下标，则将标于p处。并把(r,p)边变红。④重复上述步骤，直至全部的点都标完。L(1,p)对有向图同样可以用标号算法：例3：如图所示，有一批货物要从v1运到v9，弧旁数字表示该段路长，求最短运输路线。v1v9v8v7v6v5v4v3v23333342.55222140v1v9v8v7v6v5v4v3v

5、23333342.552221403v1v9v8v7v6v5v4v3v23333342.552221403v1v9v8v7v6v5v4v3v23333342.5522214034v1v9v8v7v6v5v4v3v23333342.5522214034v1v9v8v7v6v5v4v3v23333342.55222140345v1v9v8v7v6v5v4v3v23333342.55222140345v1v9v8v7v6v5v4v3v23333342.5522214034665v1v9v8v7v6v5v4v3v23333342.5522214034665v1v9v8v7v6v5v4v3v2

6、3333342.55222140346756v1v9v8v7v6v5v4v3v23333342.552221403467568.5练习：用Dijkstra算法求下图中v1点到v8点的最短路v25v49v64474v15v86451v37v56v7全部计算结果为：从v1到v8的最短路为v1v2v5v7v8路长为P(v8)=15.注意：该方法仅适用于全部权为非负情况，如果某边上权为负数，则算法失效。例4：企业要制定一台重要设备更新的五年计划，目标是使总费用（购置费用和维修费用之和）为最小。此设备在各年初价格及使用期中所需维修数据如下：解：用点vi表示年初。（i=1,2,…6），v6表示第

7、五年底。弧aij=（vi，vj）表示第i年初购置设备使用到第j年初的过程。对应的权期间发生的购置费用和维修费用之和。原问题转变为从v1到v6的一条最短路。v1v2v3v4v5v6162218171716304159312341302223v1v2v3v4v5v6162218171716304159312341302223v1v2v3v4v5v6162218171716304159312341302223v1v2v3v4v5v6162218171716304