资源描述：
《运筹学05-图与网络分析2-最短路》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、最短路问题最短（通）路问题是最重要的优化问题之一，例如各种管道的铺设、线路的安排、厂区的布局、设备的更新及运输网络的最小费用流等。（最短距离、费时最少、费用最省）109631702115132861722291511914397463109631702115132861722291511914397463一般的最短路问题描述：给定一个赋权有向图D=(V,A)，对每一个弧a=(vi,vj)，相应地有权w(a)=wij，又给定D中的任何两个顶点vs和vt，设P是从vs到vt的路，定义路P的权是P中所有弧之和，记为w(P)，最短路问题就是要在所有从vs到
2、vt的路中，求一条权最小的路，即一条从vs到vt的路P0使得：路P0的权称为从vs到vt的距离，记为d(vs,vt)。Dinkstra标号法这是解决网络中某一点到其它点的最短路问题时目前认为的最好方法。适用于有向图权值非负的情况求网络上的一点到其它点 的最短路有向图权值非负----Dijkstra算法Dijkstra算法的基本步骤（权值非负）1、给顶点v1标号（0），v1称为已标号点，记标号点集为V1={v1}2、在未标号点集V2中找出与标号点集V1中的顶点vi有弧相连（并且以vi为起点）的点vj，3、在第2步选出的点中，选出满足下面条件的点vk，
3、并给vk标号（l,L1k），其中l为第一标号，L1k为第二标号为从v1到vk的最短路的长度，l表示在从v1到vk的最短路上，与vk相邻的点是vl4、若最后一个顶点vn未标号，则转回第2步；若vn已标号，则从vn开始，按照第一个标号逆向追踪，直到v1，就得到从v1到vn的最短路，vn的第二个标号表示最短路的长度。5127563425527313571木器厂有六个车间，办事员经常要到各个车间了解生产进度。从办公室到各车间的路线由图1给出。找出点1（办公室）到其它各点（车间）的最短路距离、价格123252边eij或记为（vi，vj）点（vi）权wij(d
4、ij)0①从点1出发，因L11=0，在点1处标记5127563425527313571051275634255273135710从已标号的点出发，找与这些相邻点最小权数（距离）者，找到之后：标号；边变红。51275634255273135710(1,2)51275634255273135710③从已标号的点出发，找与这些相邻点最小权数（距离）者，找到之后：标号；边变红。(1,2)51275634255273135710③从已标号的点出发，找与这些相邻点最小权数（距离）者，找到之后：标号；边变红。3(1,2)51275634255273135710
5、④重复上述步骤，直至全部的点都标完。(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,4)51275634255273135710(3,7)(1,3)(1,2)(2,4)512756342552731357108(1,3)(1,2)(2,4)(3,7)5127563
6、4255273135710(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，弧旁数字表示该段路长，求最短运输路线。v1v9v8v7v6v5v4v3v23333342.55222140v1v9v8v7v6v5v4v3v23333342.552221403v1v9v8v7v6v5v4v3
7、v23333342.552221403v1v9v8v7v6v5v4v3v23333342.5522214034v1v9v8v7v6v5v4v3v23333342.5522214034v1v9v8v7v6v5v4v3v23333342.55222140345v1v9v8v7v6v5v4v3v23333342.55222140345v1v9v8v7v6v5v4v3v23333342.5522214034665v1v9v8v7v6v5v4v3v23333342.5522214034665v1v9v8v7v6v5v4v3v23333342.55222140
8、346756v1v9v8v7v6v5v4v3v23333342.552221403467568.5v1v9v8v7v6v5
