《最短路径问题-数学建模讲述》由会员分享，可在线阅读，更多相关《最短路径问题-数学建模讲述（17页珍藏版）》请在金锄头文库上搜索。
1、最短路径问题最短路径问题 主要内容主要内容 Floyd算法 Dijkstra算法 两个例子的求解 引例2：最廉价航费表的制定 引例1：最短运输路线问题 最短路径问题的0-1规划模型 3 如图的交通网络，每条弧上的数字代表车辆在该路段行如图的交通网络，每条弧上的数字代表车辆在该路段行 驶所需的时间，有向边表示单行道，无向边表示可双向驶所需的时间，有向边表示单行道，无向边表示可双向 行驶。若有一批货物要从行驶。若有一批货物要从1 1号顶点运往号顶点运往1111号顶点，问运号顶点，问运 货车应沿哪条线路行驶，才能最快地到达目的地？货车应沿哪条线路行驶，才能最快地到达目的地？ 引例引例1 1：最短运输
2、路线问题最短运输路线问题 10 23 7 4 1165 98 1 3 3 5 5 1212 2 2 1010 6 6 1 1 5 5 8 8 8 8 7 7 9 9 9 9 3 3 2 2 2 2 7 7 4 某公司在六个城市某公司在六个城市C C 1 1 ,C,C 2 2 ,C,C 3 3 ,C,C 4 4 ,C,C 5 5 ,C,C 6 6 都有分公司，都有分公司， 公司成员经常往来于它们之间，已知从公司成员经常往来于它们之间，已知从CiCi到到C C j j 的直达航的直达航 班票价由下述矩阵的第班票价由下述矩阵的第i i行，第行，第j j列元素给出（列元素给出（ 表示无表示无 直达航班
3、），该公司想算出一张任意两个城市之间的最直达航班），该公司想算出一张任意两个城市之间的最 廉价路线航费表。廉价路线航费表。 引例引例2 2：最廉价航费表的制定最廉价航费表的制定 5 最短路径问题最短路径问题 l定义：设P(u,v)是加权图G中从u到v的路径,则该 路径上的边权之和称为该路径的权,记为w(P). 从u到 v的路径中权最小者 P*(u,v)称为u到v的最短路径. 10 23 7 4 1165 98 1 3 3 5 5 1212 2 2 1010 6 6 1 1 5 5 8 8 8 8 7 7 9 9 9 9 3 3 2 2 2 2 7 7 最短路径算法最短路径算法 Dijkstra
4、Dijkstra算法算法 使用范围使用范围: : 1)1)寻求从一固定顶点到其余各点的最短路径寻求从一固定顶点到其余各点的最短路径; ; 2)2)有向图、无向图和混合图有向图、无向图和混合图; ; 3)3)权非负权非负. . 算法思路：算法思路： 采用标号作业法采用标号作业法, ,每次迭代产生一个永久标号每次迭代产生一个永久标号, , 从而生长一颗以从而生长一颗以v v 0 0 为根的最短路树为根的最短路树, ,在这颗树上每个在这颗树上每个 顶点与根节点之间的路径皆为最短路径顶点与根节点之间的路径皆为最短路径. . 10 23 7 4 11 65 98 1 3 3 5 5 1 1 2 2 2
5、2 1 1 0 0 6 6 1 1 5 5 8 8 8 8 7 7 9 9 9 9 3 3 2 2 2 2 7 7 DijkstraDijkstra算法算法算法步骤 S: 具有永久标号的顶点集; l(v): v的标记; f(v):v的父顶点,用以确定最短路径; 输入加权图的带权邻接矩阵w=w(vi,vj)nxm. 1)初始化 令l(v0)=0,S=; vv0 ,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
6、)u; 3)重复步骤2), 直到所有顶点都在S中为止. MATLABMATLAB程序（程序（DijkstraDijkstra算法）算法） function min,path=dijkstra(w,start,terminal)function min,path=dijkstra(w,start,terminal) n=size(w,1); label(start)=0; f(start)=start;n=size(w,1); label(start)=0; f(start)=start; for i=1:nfor i=1:n if i=start if i=start label(i)=inf
7、; label(i)=inf; end, endend, end s(1)=start; u=start;s(1)=start; u=start; while length(s)(label(u)+w(u,v) label(v)=(label(u)+w(u,v); f(v)=u; label(v)=(label(u)+w(u,v); f(v)=u; end, end, end end, end, end v1=0;v1=0; k=inf; k=inf; for i=1:n for i=1:n ins=0; ins=0; for j=1:length(s) for j=1:length(s) i
8、f i=s(j) if i=s(j) ins=1; ins=1; end, end end, end if ins=0 if ins=0 v=i; v=i; if klabel(v) if klabel(v) k=label(v); v1=v; k=label(v); v1=v; end, end, end end, end, end s(length(s)+1)=v1; s(length(s)+1)=v1; u=v1; u=v1; endend min=label(terminal); min=label(terminal); path(1)=terminal;path(1)=termina
9、l; i=1; i=1; while path(i)=startwhile path(i)=start path(i+1)=f(path(i); path(i+1)=f(path(i); i=i+1 ; i=i+1 ; endend path(i)=start; path(i)=start; L=length(path);L=length(path); path=path(L:-1:1);path=path(L:-1:1); 9 最短路径算法最短路径算法 DijkstraDijkstra算法程序的使用说明：算法程序的使用说明： 调用格式为调用格式为 min,path=dijkstra(w,st
10、art,terminal)min,path=dijkstra(w,start,terminal), , 其中输入变量其中输入变量w w为所求图的带权邻接矩阵，为所求图的带权邻接矩阵，start, start, terminalterminal分别为路径的起点和终点的号码。分别为路径的起点和终点的号码。返回返回startstart 到到terminalterminal的最短路径的最短路径pathpath及其长度及其长度min.min. 注意：顶点的编号从注意：顶点的编号从1 1开始连续编号。开始连续编号。 最短路径算法最短路径算法 FloydFloyd算法算法 使用范围使用范围: : 1)1)求
11、每对顶点的最短路径求每对顶点的最短路径; ; 2)2)有向图、无向图和混合图有向图、无向图和混合图; ; 算法思想算法思想: : 直接在图的带权邻接矩阵中用插入顶点的方法依次直接在图的带权邻接矩阵中用插入顶点的方法依次 递推地构造出递推地构造出n n个矩阵个矩阵D(1), D(2), , D(n), D(n)D(1), D(2), , D(n), D(n)是是 图的距离矩阵图的距离矩阵, , 同时引入一个后继点矩阵记录两点同时引入一个后继点矩阵记录两点 间的最短路径间的最短路径. . 10 23 7 4 11 65 98 1 3 3 5 5 1 1 2 2 2 2 1 1 0 0 6 6 1
12、1 5 5 8 8 8 8 7 7 9 9 9 9 3 3 2 2 2 2 7 7 FloydFloyd算法算法算法步骤 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+1 3）重复2)直到k=n+1 MATLABMATLAB程序（程序（F
13、loydFloyd算法）算法） function D,path,min1,path1=floyd(a,start,terminal)function D,path,min1,path1=floyd(a,start,terminal) D=a;n=size(D,1);path=zeros(n,n);D=a;n=size(D,1);path=zeros(n,n); for i=1:nfor i=1:n for j=1:n for j=1:n if D(i,j)=inf if D(i,j)=inf path(i,j)=j; path(i,j)=j; end, end, endend, end, en
14、d for k=1:nfor k=1:n for i=1:n for i=1:n for j=1:n for j=1:n if D(i,k)+D(k,j)D(i,j) if D(i,k)+D(k,j)D(i,j) D(i,j)=D(i,k)+D(k,j); D(i,j)=D(i,k)+D(k,j); path(i,j)=path(i,k); path(i,j)=path(i,k); end, end, end,endend, end, end,end if nargin=3if nargin=3 min1=D(start,terminal); min1=D(start,terminal); m
15、(1)=start; m(1)=start; i=1; i=1; path1= ; path1= ; while path(m(i),terminal)=terminal while path(m(i),terminal)=terminal k=i+1; k=i+1; m(k)=path(m(i),terminal); m(k)=path(m(i),terminal); i=i+1; i=i+1; end end m(i+1)=terminal; m(i+1)=terminal; path1=m; path1=m; end end 13 最短路径算法最短路径算法 FloydFloyd算法程序的使用说明：算法程序的使用说明： 1. D, path=floyd(a), 1. D, path=floyd(a), 返回矩阵返回矩阵D, path D, path 。其中。其中a a是所求是所求 图的带权邻接矩阵，图的带权邻接矩阵，D(i,j)D(i,j)表示表示i i到到j j的最短距离的最短距离; ; path(i,j)path(i,j)表示表示i i与与j j之间的最短路径上顶点之间的最短路径上顶点i i的后继点的后继点. . 2. D, path, min1, path1= floyd(a,i,j) 2. D,
