最短路径问题-数学建模ppt课件.ppt

Floyd算法Dijkstra算法两个例子的求解引例2：最廉价航费表的制定引例1：最短运输路线问题最短路径问题的0-1规划模型3102374116598140504025105001520251501020402010010252520100551025255505l定义：设定义：设P(u,v)是加权图是加权图G中从中从u到到v的路径的路径,则该路则该路径上的边权之和称为该路径的权径上的边权之和称为该路径的权,记为记为w(P). 从从u到到v的路径中权最小者的路径中权最小者 P*(u,v)称为称为u到到v的最短路径的最短路径.10237411659811023741165981算法步骤算法步骤S: 具有永久标号的顶点集具有永久标号的顶点集;l(v): v的标记的标记; f(v):v的父顶点的父顶点,用以确定最短路径用以确定最短路径; 输入加权图的带权邻接矩阵输入加权图的带权邻接矩阵w=w(vi,vj)nxm.1)初始化初始化 令令l(v0)=0,S= ; v v0 ,l(v)= ;2)更新更新l(v), f(v) 寻找不在寻找不在S中的顶点中的顶点u,使使l(u)为最小为最小.把把u加入到加入到S中中,然后对所有不在然后对所有不在S中的顶点中的顶点v,如如l(v)l(u)+w(u,v),则则更新更新l(v),f(v), 即即 l(v)l(u)+w(u,v),f(v)u;3)重复步骤重复步骤2), 直到所有顶点都在直到所有顶点都在S中为止中为止.91023741165981算法步骤算法步骤 d(i,j) : i到到j的距离的距离; path(i,j): i到到j的路径上的路径上i的后继点的后继点; 输入带权邻接矩阵输入带权邻接矩阵a(i,j).1）赋初值）赋初值 对所有对所有i,j, d(i,j)a(i,j) , path(i,j)j,k=l.2）更新）更新d(i,j) , path(i,j) 对所有对所有i,j, 若若d(i,k)+d(k,j)d(i,j),则则 d(i,j)d(i,k)+d(k,j) , path(i,j)path(i,k) , k k+13）重复）重复2)直到直到k=n+11314102374116598115运行上页程序输出：运行上页程序输出：dis = 21path = 1 8 9 10 11 因此顶点因此顶点1到顶点到顶点11的最短路径为的最短路径为18 9 10 11, 其长度为其长度为21。1605040251050015202515010204020100102525201005510252555005040251050015202515010204020100102525201005510252555018 假设图有假设图有 n 个顶点，现需要求从顶点个顶点，现需要求从顶点1到顶点到顶点n的的最短路径最短路径.最短路径问题的最短路径问题的0-10-1规划模型规划模型 设决策变量为设决策变量为xij , 当顶点当顶点1至顶点至顶点n的路上含弧的路上含弧(i,j) 时，时，xij=1；否则；否则xij=0. 其数学规划表达式为其数学规划表达式为( , )11( , )( , )min ; 1,1,. . 1, ; 0,1, . 01,( , ). ijiji jEnnijjijji jEj iEijw xistxxininxi jE 或19最短路径问题的最短路径问题的0-10-1规划模型规划模型 例例 （有向图最短路问题）（有向图最短路问题） 在下图中，用点表示城市，现在下图中，用点表示城市，现有有 共共7个城市个城市.点与点之间的连线表示城市间有道点与点之间的连线表示城市间有道路相连路相连.连线旁的数字表示道路的长度连线旁的数字表示道路的长度.现计划从城市现计划从城市 到城市到城市 铺设一条天然气管道，请设计出最小价格管道铺设方案铺设一条天然气管道，请设计出最小价格管道铺设方案. 12123, ,AB B C C C DAD本质是求从城市本质是求从城市 到城市到城市 的一条最短路的一条最短路AD20最短路径问题的最短路径问题的0-10-1规划模型规划模型 解：解：写出相应的写出相应的LINGO程序，程序，MODEL: 1! We have a network of 7 cities. We want to find 2 the length of the shortest route from city 1 to city 7; 3 4sets: 5 ! Here is our primitive set of seven cities; 6 cities/A, B1, B2, C1, C2, C3, D/; 7 8 ! The Derived set roads lists the roads that 9 exist between the cities; 21最短路径问题的最短路径问题的0-10-1规划模型规划模型 10 roads(cities, cities)/ 11 A,B1 A,B2 B1,C1 B1,C2 B1,C3 B2,C1 B2,C2 B2,C3 12 C1,D C2,D C3,D/: w, x; 13 endsets 14 15 data: 16 ! Here are the distances that correspond 17 to above links; 18 w = 2 4 3 3 1 2 3 1 1 3 4; 19 enddata 22最短路径问题的最短路径问题的0-10-1规划模型规划模型 20 21 n=size(cities); ! The number of cities; 22 min=sum(roads: w*x); 23 for(cities(i) | i #ne# 1 #and# i #ne# n: 24 sum(roads(i,j): x(i,j) = sum(roads(j,i): x(j,i); 25 sum(roads(i,j)|i #eq# 1 : x(i,j)=1; END23最短路径问题的最短路径问题的0-10-1规划模型规划模型 在上述程序中，在上述程序中， 21句中的句中的n=size(cities)是计算集是计算集cities的个数，这里的计算结果是的个数，这里的计算结果是 , 这样编写方法目的这样编写方法目的在于提高程序的通用性在于提高程序的通用性.22句表示目标函数句表示目标函数, 即求道路的最即求道路的最小权值小权值.23, 24句表示约束中句表示约束中 的情况，即最短路中的情况，即最短路中中间点的约束条件中间点的约束条件.25句表示约束中句表示约束中 的情况，即最短的情况，即最短路中起点的约束路中起点的约束.7n 1,iin1i 约束中约束中 的情况，也就是最短路中终点的情况，没的情况，也就是最短路中终点的情况，没有列在程序中，因为终点的约束方程与前个方程相关有列在程序中，因为终点的约束方程与前个方程相关.当然，如果你将此方程列入到当然，如果你将此方程列入到LINGO程序中，计算时程序中，计算时也不会出现任何问题，因为也不会出现任何问题，因为LINGO软件可以自动删除软件可以自动删除描述线性规划可行解中的多余方程描述线性规划可行解中的多余方程.in24最短路径问题的最短路径问题的0-10-1规划模型规划模型 LINGO软件计算结果（仅保留非零变量）如下软件计算结果（仅保留非零变量）如下Global optimal solution found at iteration: 0 Objective value: 6.000000 Variable Value Reduced Cost X( A, B1) 1.000000 0.000000 X( B1, C1) 1.000000 0.000000 X( C1, D) 1.000000 0.000000 即最短路是即最短路是 , 最短路长为最短路长为6个单位个单位.11ABCD25最短路径问题的最短路径问题的0-10-1规划模型规划模型 例例（无向图的最短路问题）求下图中（无向图的最短路问题）求下图中 到到 的最短路的最短路.1v11v 本例是处理无向图的最短路问题，在处理方式上与有向图本例是处理无向图的最短路问题，在处理方式上与有向图的最短路有一些差别的最短路有一些差别.26最短路径问题的最短路径问题的0-10-1规划模型规划模型 解：解： 对于无向图的最短路问题，可以这样理解，从点对于无向图的最短路问题，可以这样理解，从点 到点到点 和点和点 到点到点 的边看成有向弧，其他各条边均看成有的边看成有向弧，其他各条边均看成有不同方向的双弧，因此，可以按照前面介绍有向图的最短路不同方向的双弧，因此，可以按照前面介绍有向图的最短路问题来编程序，但按照这种方法编写问题来编程序，但按照这种方法编写LINGO程序相当于边程序相当于边（弧）增加了一倍（弧）增加了一倍.这里选择邻接矩阵和赋权矩阵的方法编写这里选择邻接矩阵和赋权矩阵的方法编写LINGO程序程序.1viviv11vMODEL: 1 sets: 2 cities/1.11/; 3 roads(cities, cities): p, w, x; 4 endsets 27最短路径问题的最短路径问题的0-10-1规划模型规划模型 5 data: 6 p = 0 1 1 1 0 0 0 0 0 0 0 7 0 0 1 0 1 0 0 0 0 0 0 8 0 1 0 1 1 1 1 0 0 0 0 9 0 0 1 0 0 0 1 0 0 0 0 10 0 1 1 0 0 1 0 1 1 0 0 11 0 0 1 0 1 0 1 0 1 0 0 12 0 0 1 1 0 1 0 0 1 1 0 13 0 0 0 0 1 0 0 0 1 0 1 14 0 0 0 0 1 1 1 1 0 1 1 15 0 0 0 0 0 0 1 0 1 0 1 16 0 0 0 0 0 0 0 0 0 0 0;28最短路径问题的最短路径问题的0-10-1规划模型规划模型 17 w = 0 2 8 1 0 0 0 0 0 0 0 18 2 0 6 0 1 0 0 0 0 0 0 19 8 6 0 7 5 1 2 0 0 0 0 20 1 0 7 0 0 0 9 0 0 0 0 21 0 1 5 0 0 3 0 2 9 0 0 22 0 0 1 0 3 0 4 0 6 0 0 23 0 0 2 9 0 4 0 0 3 1 0 24 0 0 0 0 2 0 0 0 7 0 9 25 0 0 0 0 9 6 3 7 0 1 2 26 0 0 0 0 0 0 1 0 1 0 4 27 0 0 0 0 0 0 0 9 2 4 0; 28 enddata29最短路径问题的最短路径问题的0-10-1规划模型规划模型 29n=size(cities); 30min=sum(roads:w*x); 31for(cities(i) | i #ne# 1 #and# i #ne# n: 32 sum(cities(j): p(i,j)*x(i,j) 33 =sum(cities(j): p(j,i)*x(j,i); 34sum(cities(j): p(1,j)*x(1,j)=1; END30最短路径问题的最短路径问题的0-10-1规划模型规划模型 在上述程序中在上述程序中，第，第6行到第行到第16行给出了图的邻接矩阵行给出了图的邻接矩阵 ， 到到 和和 到到 的边按单向计算，其余边双的边按单向计算，其余边双向计算向计算.第第17行到第行到第27行给出了图的赋权矩阵行给出了图的赋权矩阵 , 注意：由注意：由于有了邻接矩阵于有了邻接矩阵 ，两点无道路连接时，权值可以定义为，两点无道路连接时，权值可以定义为0. 其它的处理方法基本上与有向图相同其它的处理方法基本上与有向图相同.P1v234,vvv8910,vvv11vWP用用LINGO软件求解，得到（仅保留非零变量）软件求解，得到（仅保留非零变量） Global optimal solution found at iteration: 2 0 Objective value: 13.00000 31最短路径问题的最短路径问题的0-10-1规划模型规划模型 Variable Value Reduced Cost X( 1, 2) 1.000000 0.000000 X( 2, 5) 1.000000 0.000000 X( 3, 7) 1.000000 0.000000 X( 5, 6) 1.000000 0.000000 X( 6, 3) 1.000000 0.000000 X( 7, 10) 1.000000 0.000000 X( 9, 11) 1.000000 0.000000 X( 10, 9) 1.000000 0.000000 即最短路径为即最短路径为1256371011最短路长度最短路长度为为13.