《经典最短路径问题 数学建模ppt课件.ppt》由会员分享，可在线阅读，更多相关《经典最短路径问题 数学建模ppt课件.ppt（31页珍藏版）》请在三一办公上搜索。
1、最短路径问题,Mathematica Modeling,参考书：1.傅鹂 龚劬 刘琼荪 何中市 数学实验科学出版社2.张绍民 李淑华 数据结构教程C语言版中国电力出版社,主要内容,Floyd算法,Dijkstra算法,两个例子的求解,引例2：最廉价航费表的制定,引例1：最短运输路线问题,最短路径问题的0-1规划模型,3,如图的交通网络，每条弧上的数字代表车辆在该路段行驶所需的时间，有向边表示单行道，无向边表示可双向行驶。若有一批货物要从1号顶点运往11号顶点，问运货车应沿哪条线路行驶，才能最快地到达目的地？,引例1：最短运输路线问题,4,某公司在六个城市C1,C2,C3,C4,C5,C6都有分
2、公司，公司成员经常往来于它们之间，已知从Ci到Cj的直达航班票价由下述矩阵的第i行，第j列元素给出（表示无直达航班），该公司想算出一张任意两个城市之间的最廉价路线航费表。,引例2：最廉价航费表的制定,5,最短路径问题,定义：设P(u,v)是加权图G中从u到v的路径,则该路径上的边权之和称为该路径的权,记为w(P). 从u到v的路径中权最小者 P*(u,v)称为u到v的最短路径.,最短路径算法,Dijkstra算法使用范围:寻求从一固定顶点到其余各点的最短路径;有向图、无向图和混合图;权非负.算法思路： 采用标号作业法,每次迭代产生一个永久标号, 从而生长一颗以v0为根的最短路树,在这颗树上每个
3、顶点与根节点之间的路径皆为最短路径.,Dijkstra算法算法步骤,S: 具有永久标号的顶点集;l(v): v的标记; f(v):v的父顶点,用以确定最短路径; 输入加权图的带权邻接矩阵w=w(vi,vj)nxm.初始化 令l(v0)=0,S=; vv0 ,l(v)=;更新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;重复步骤2), 直到所有顶点都在S中为止.,MATLAB程序（Dijkstra算法）,function min
4、,path=dijkstra(w,start,terminal)n=size(w,1); label(start)=0; f(start)=start;for i=1:n if i=start label(i)=inf;end, ends(1)=start; u=start;while length(s)(label(u)+w(u,v) label(v)=(label(u)+w(u,v); f(v)=u; end, end, end,v1=0; k=inf; for i=1:n ins=0; for j=1:length(s) if i=s(j) ins=1; end, end if ins=
5、0 v=i; if klabel(v) k=label(v); v1=v; end, end, end s(length(s)+1)=v1; u=v1;end,min=label(terminal); path(1)=terminal;i=1; while path(i)=start path(i+1)=f(path(i); i=i+1 ;end path(i)=start;L=length(path);path=path(L:-1:1);,9,最短路径算法,Dijkstra算法程序的使用说明： 调用格式为 min,path=dijkstra(w,start,terminal), 其中输入变量
6、w为所求图的带权邻接矩阵，start, terminal分别为路径的起点和终点的号码。返回start到terminal的最短路径path及其长度min.注意：顶点的编号从1开始连续编号。,最短路径算法,Floyd算法使用范围:求每对顶点的最短路径;有向图、无向图和混合图;算法思想: 直接在图的带权邻接矩阵中用插入顶点的方法依次递推地构造出n个矩阵D(1), D(2), , D(n), D(n)是图的距离矩阵, 同时引入一个后继点矩阵记录两点间的最短路径.,Floyd算法算法步骤,d(i,j) : i到j的距离; path(i,j): i到j的路径上i的后继点; 输入带权邻接矩阵a(i,j).1
7、）赋初值 对所有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+1,MATLAB程序（Floyd算法）,function D,path,min1,path1=floyd(a,start,terminal)D=a;n=size(D,1);path=zeros(n,n);for i=1:n for j=1:n if D(i,j)=inf path(i,
8、j)=j;end, end, endfor k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)D(i,j) D(i,j)=D(i,k)+D(k,j); path(i,j)=path(i,k);end, end, end,end,if nargin=3 min1=D(start,terminal); m(1)=start; i=1; path1= ; while path(m(i),terminal)=terminal k=i+1; m(k)=path(m(i),terminal); i=i+1; end m(i+1)=terminal; path1=m;end
9、,13,最短路径算法,Floyd算法程序的使用说明：1. D, path=floyd(a), 返回矩阵D, path 。其中a是所求图的带权邻接矩阵，D(i,j)表示i到j的最短距离; path(i,j)表示i与j之间的最短路径上顶点i的后继点.2. D, path, min1, path1= floyd(a,i,j) 返回矩阵D, path; 并返回i与j之间的最短距离min1和最短路径path1.,14,edge= 2,3,1,3,3,5,4, 4,1,7,6,6,5, 5,11, 1,8,6,9,10,8,9, 9,10;. 3,4,2,7,5,3,5,11,7,6,7,5,6,11,
10、5, 8,1,9,5,11,9,8,10,9;. 3,5,8,5,6,6,1,12,7,9,9,2,2,10,10,8,8,3,7, 2, 9,9, 2, 2;n=11; weight=inf*ones(n, n);for i=1:n weight(i, i)=0;endfor i=1:size(edge,2)weight(edge(1, i), edge(2, i)=edge(3, i);enddis, path=dijkstra(weight, 1, 11),引例1的Matlab求解,15,运行上页程序输出：dis = 21path = 1 8 9 10 11 因此顶点1到顶点11的最短路
11、径为18 9 10 11, 其长度为21。,引例1的求解,16,建立脚本m文件如下：a= 0,50,inf,40,25,10;50,0,15,20,inf,25;inf,15,0,10,20,inf;40,20,10,0,10,25;25,inf,20,10,0,55;10,25,inf,25,55,0;D, path=floyd(a)运行便可输出结果。,引例2的Matlab求解,运行输出结果： D = 0 35 45 35 25 10 35 0 15 20 30 25 45 15 0 10 20 35 35 20 10 0 10 25 25 30 20 10 0 35 10 25 35 25
12、 35 0path = 1 6 5 5 5 6 6 2 3 4 4 6 5 2 3 4 5 4 5 2 3 4 5 6 1 4 3 4 5 1 1 2 4 4 1 6,D便是最廉价的航费表，要求飞行路线，由path矩阵可以得到，比如2到5的路线：path(2,5)=4, path(4,5)=5,因此，应为24 5,18,假设图有 n 个顶点，现需要求从顶点1到顶点n的最短路径.,最短路径问题的0-1规划模型,设决策变量为xij , 当顶点1至顶点n的路上含弧(i,j) 时，xij=1；否则xij=0. 其数学规划表达式为,19,最短路径问题的0-1规划模型,例 （有向图最短路问题） 在下图中，
13、用点表示城市，现有 共7个城市.点与点之间的连线表示城市间有道路相连.连线旁的数字表示道路的长度.现计划从城市 到城市 铺设一条天然气管道，请设计出最小价格管道铺设方案.,本质是求从城市 到城市 的一条最短路,20,最短路径问题的0-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 seve
14、n 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-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 co
15、rrespond 17 to above links; 18 w = 2 4 3 3 1 2 3 1 1 3 4; 19 enddata,22,最短路径问题的0-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; END,23,最
16、短路径问题的0-1规划模型,在上述程序中， 21句中的n=size(cities)是计算集cities的个数，这里的计算结果是 , 这样编写方法目的在于提高程序的通用性.22句表示目标函数, 即求道路的最小权值.23, 24句表示约束中 的情况，即最短路中中间点的约束条件.25句表示约束中 的情况，即最短路中起点的约束.,约束中 的情况，也就是最短路中终点的情况，没有列在程序中，因为终点的约束方程与前个方程相关.当然，如果你将此方程列入到LINGO程序中，计算时也不会出现任何问题，因为LINGO软件可以自动删除描述线性规划可行解中的多余方程.,24,最短路径问题的0-1规划模型,LINGO软件
17、计算结果（仅保留非零变量）如下,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个单位.,25,最短路径问题的0-1规划模型,例（无向图的最短路问题）求下图中 到 的最短路.,本例是处理无向图的最短路问题，在处理方式上与有向图的最短路有一些差别.,2
18、6,最短路径问题的0-1规划模型,解： 对于无向图的最短路问题，可以这样理解，从点 到点 和点 到点 的边看成有向弧，其他各条边均看成有不同方向的双弧，因此，可以按照前面介绍有向图的最短路问题来编程序，但按照这种方法编写LINGO程序相当于边（弧）增加了一倍.这里选择邻接矩阵和赋权矩阵的方法编写LINGO程序.,MODEL: 1 sets: 2 cities/1.11/; 3 roads(cities, cities): p, w, x; 4 endsets,27,最短路径问题的0-1规划模型,5 data: 6 p = 0 1 1 1 0 0 0 0 0 0 0 7 0 0 1 0 1 0
19、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-1规划模型,17 w = 0 2 8 1 0 0 0 0 0 0 0 18 2 0 6 0 1 0 0 0
20、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 enddata,29,最短路径问题的0-1规划模型,29n=size(cities); 30min=sum(roads:w*x);
21、 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; END,30,最短路径问题的0-1规划模型,在上述程序中，第6行到第16行给出了图的邻接矩阵 ， 到 和 到 的边按单向计算，其余边双向计算.第17行到第27行给出了图的赋权矩阵 , 注意：由于有了邻接矩阵 ，两点无道路连接时，权值可以定义为0. 其它的处理方法基本上与有向图相同.,用LINGO软件求解，得到（
22、仅保留非零变量） Global optimal solution found at iteration: 2 0 Objective value: 13.00000,31,最短路径问题的0-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,即最短路径为,最短路长度为13.,
