运筹学05_图与网络分析2-最短路.ppt

《运筹学05_图与网络分析2-最短路.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、最短路问题最短（通）路问题是最重要的优化问题之一，例如各种管道的铺设、线路的安排、厂区的布局、设备的更新及运输网络的最小费用流等。（最短距离、费时最少、费用最省）破圈法是：任取一圈，去掉圈中最长边，直到无圈避圈法是：去掉图中所有边，从最短边开始添加，加边的过程中不能形成圈，直到连通（n－1条边）一个连通的无向图叫做树树无圈，但不相邻的两个点之间加一条边，得到一个圈树中任意两个顶点之间，恰有且仅有一条链下图中右图是支撑树v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10e11(a)e5e7v1v2v5v6v7e1e6e8(b)一个连通图能一笔画的条件

2、是：它没有奇点；或者它恰好有一个奇点。一个图有5个点，８条边。这个图一定是A．连通图B．树C．完全图D．不连通图连通图G有n个点，其部分树是T，则有A.T有n个点n条边B.T的长度等于G的每条边的长度之和C.T有n个点n－1条边D.T有n－1个点n条边某人要从上海乘飞机到奥地利首都维也纳，他希望选择一条航线，经过转机，使他在空中飞行的时间尽可能短。该问题可转化为A.最短路线问题求解B.最大流量问题求解C.最小树问题求解D.中国邮递员问题求109631702115132861722291511914397463109631702115132861722291511914

3、397463一般的最短路问题描述：给定一个赋权有向图D=(V,A)，对每一个弧a=(vi,vj)，相应地有权w(a)=wij，又给定D中的任何两个顶点vs和vt，设P是从vs到vt的路，定义路P的权是P中所有弧之和，记为w(P)，最短路问题就是要在所有从vs到vt的路中，求一条权最小的路，即一条从vs到vt的路P0使得：路P0的权称为从vs到vt的距离，记为d(vs,vt)。Dinkstra标号法这是解决网络中某一点到其它点的最短路问题时目前认为的最好方法。适用于有向图权值非负的情况求网络上的一点到其它点的最短路有向图权值非负----Dijkstra算法Dijkst

4、ra算法的基本步骤（权值非负）1、给顶点v1标号（0），v1称为已标号点，记标号点集为V1={v1}2、在未标号点集V2中找出与标号点集V1中的顶点vi有弧相连（并且以vi为起点）的点vj，3、在第2步选出的点中，选出满足下面条件的点vk，并给vk标号（l,L1k），其中l为第一标号，L1k为第二标号为从v1到vk的最短路的长度，l表示在从v1到vk的最短路上，与vk相邻的点是vl4、若最后一个顶点vn未标号，则转回第2步；若vn已标号，则从vn开始，按照第一个标号逆向追踪，直到v1，就得到从v1到vn的最短路，vn的第二个标号表示最短路的长度。51275634255

5、27313571木器厂有六个车间，办事员经常要到各个车间了解生产进度。从办公室到各车间的路线由图1给出。找出点1（办公室）到其它各点（车间）的最短路距离、价格123252边eij或记为（vi，vj）点（vi）权wij(dij)0①从点1出发，因L11=0，在点1处标记5127563425527313571051275634255273135710从已标号的点出发，找与这些相邻点最小权数（距离）者，找到之后：标号；边变红。51275634255273135710(1,2)51275634255273135710③从已标号的点出发，找与这些相邻点最小权数（距离）者，找到

6、之后：标号；边变红。(1,2)51275634255273135710③从已标号的点出发，找与这些相邻点最小权数（距离）者，找到之后：标号；边变红。3(1,2)51275634255273135710④重复上述步骤，直至全部的点都标完。(1,3)(1,2)51275634255273135710④重复上述步骤，直至全部的点都标完。4(1,2)(1,3)51275634255273135710④重复上述步骤，直至全部的点都标完。(2,4)(1,3)(1,2)(4,4)51275634255273135710④重复上述步骤，直至全部的点都标完。7(1,3)(1,2)(2,

7、4)51275634255273135710(3,7)(1,3)(1,2)(2,4)512756342552731357108(1,3)(1,2)(2,4)(3,7)51275634255273135710(6,8)(1,3)(1,2)(2,4)(3,7)51275634255273135710(1,3)(1,2)(2,4)(3,7)(6,8)(5,13)51275634255273135710(1,2)(1,3)(2,4)(3,7)(6,8)(5,13)对有向图同样可以用标号算法：例2如图，有一批货物要从v1运到v9，弧旁数字表示该段路长，求最短运