最短路径问题最短路径问题最短路径问题最短路径问题参考书：参考书：1. 1. 傅鹂傅鹂 龚劬2. 2. 张绍民张绍民 李淑华龚劬 刘琼荪刘琼荪 何中市李淑华 《何中市 《《数据结构教程数据结构教程C C语言版《数学实验数学实验》 》 科学出版社语言版》 》 中国电力出版社中国电力出版社科学出版社主讲： 重庆大学主讲： 重庆大学龚龚 劬劬主 要内容主 要内容引例１： 最短运输路线问题Ｆ ｌｏ ｙ ｄ 算法Ｆ ｌｏ ｙ ｄ 算法Ｄ ｉｊｋ ｓｔｒａ 算法引例２： 最廉价航费表的制定两个例子的求解最短路径问题的0-1规划模型如图的交通网络如图的交通网络， ， 每条弧上的数字代表车辆在该路段行每条弧上的数字代表车辆在该路段行驶所需的时间驶所需的时间有向边表示单行道有向边表示单行道驶所需的时间驶所需的时间， ， 有向边表示单行道有向边表示单行道， ， 无向边表示可双向行驶行驶。 。 若有一批货物要从若有一批货物要从1 1号顶点运往号顶点运往11货车应沿哪条线路行驶货车应沿哪条线路行驶， ， 才能最快地到达目的地才能最快地到达目的地？ ？无向边表示可双向无向边表示可双向无向边表示可双向11号顶点号顶点， ， 问运引例引例１ １： ： 最短运输路线问题最短运输路线问题问运2343 35 506 61 15 58 87 77 72 22 23 28 89 99 93 32 27 7某公司在六个城市某公司在六个城市C C1 1, C公司成员经常往来于它们之间公司成员经常往来于它们之间公司成员经常往来于它们之间公司成员经常往来于它们之间， ， 已知从班票价由下述矩阵的第班票价由下述矩阵的第i i行直达航班直达航班） ） ， ，该公司想算出一张任意两个城市之间的最该公司想算出一张任意两个城市之间的最廉价路线航费表廉价路线航费表。
。050∞150∞, C2 2, C, C3 3, C, C4 4, C已知从已知从Ci Ci到已知从Ci第j j列元素给出列元素给出（ （∞ ∞表示无, C5 5, C, C6 6都有分公司都有分公司数据结构最短路径ppt， ，到C C 的直达航的直达航Ci到到C Cj j的直达航的直达航引例引例２ ２： ： 最廉价航费表的制定最廉价航费表的制定行数据结构最短路径ppt-最短路径问题（精品ＰＰＴ）， ， 第表示无4025∞∞∞∞最短路径问题最短路径问题定义： 设P(u,v)是加权图G中从u到v的路径,则该路径上的边权之和称为该路径的权,记为w(P). 从u到v的路径中权最小者 P*(u,v)称为u到v的最短路径.2343 35 66 61 11 18 88 85 58 87 79 99 93 32 22 27 7最短路径算法最短路径算法算法使用范围: :算法 35 51 12 22 22 21 10 06 6 1 15 58 88 88 87 79 93 392 27 72 2使用范围1) 1) 寻求从一固定顶点到其余各点的最短路径寻求从一固定顶点到其余各点的最短路径; ;2) 2) 有向图、 无向图和混合图有向图、 无向图和混合图; ;3) 3) 权非负权非负. .1089 9算法思路：算法思路：采用标号作业法采用标号作业法, ,每次迭代产生一个永久标号每次迭代产生一个永久标号, , 从而生长一颗以从而生长一颗以v v0 0为根的最短路树为根的最短路树, ,在这颗树上每在这颗树上每个顶点与根节点之间的路径皆为最短路径个顶点与根节点之间的路径皆为最短路径. .算法算法————算法步骤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中的顶点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中为止.程序（ [min,path]=(w,start,) [min,path]=(w,start,)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:nif i~= i~=(i)=inf;label(i)=inf;path(1)=;path(1)=;( );( );end, , ends(1)=start; u=start;s(1)=start; u=start;while (s)< (s)<nfor i=1:nfor i=1:nins=0;ins=0;for j=1:(s)for j=1:(s)if i==s(j)if i==s(j)=path(L:path=path(L:- -1:1);ins=1;ins=1;end, , endif ins==0if ins==0v=i;v=i;if label(v)>(label(u)+w(u,v))if label(v)>(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:nfor i 1:nfor i=1:nfor i=1:nmin=label(); min=label(); ②②②②ins=0;ins=0;for j=1:(s)for j=1:(s)if i==s(j)if i==s(j)ins=1;ins=1;end, , endif ins==0if ins==0v=i;v=i;; ;if k>label(v)if k>label(v)k=label(v); v1=v;k=label(v); v1=v;end, end, , end, ends((s)+1)=v1; s((s)+1)=v1; u=v1;u=v1;=1; i=1; while path(i)~= path(i)~=(i+1)=f(path(i));path(i+1)=f(path(i));i=i+1 ;i=i+1 ;(i)=start;path(i)=start;L=(path);L=(path);path=path(L:path=path(L:- -1:1);1:1);1:1);①①③③最短路径算法最短路径算法算法程序的使用说明：算法程序的使用说明：调用格式为调用格式为[min,path]=(w,start,), [min,path]=(w,start,), 其中输入变量其中输入变量w w为所求图的带权邻接矩阵，为所求图的带权邻接矩阵， start, 分别为路径的起点和终点的号码。
返回分别为路径的起点和终点的号码。 返回start分别为路径的起点和终点的号码分别为路径的起点和终点的号码到到的最短路径的最短路径及其长度start, 返回返回及其长度min.min.注意： 顶点的编号从注意： 顶点的编号从1 1开始连续编号。开始连续编号。最短路径算法最短路径算法算法算法 35 51 12 22 22 21 10 06 6 1 15 58 88 88 87 79 93 392 27 72 2使用范围使用范围: :1) 1) 求每对顶点的最短路径求每对顶点的最短路径; ;2) 2) 有向图、 无向图和混合图有向图、 无向图和混合图; ;算法思想算法思想: :直接在图的带权邻接矩阵中用插入顶点的方法依次直接在图的带权邻接矩阵中用插入顶点的方法依次直接在图的带权邻接矩阵中用插入顶点的方法依次直接在图的带权邻接矩阵中用插入顶点的方法依次递推地构造出递推地构造出n n个矩阵个矩阵D(1), D(2), …, D(n), D(n)D(1), D(2), …, D(n), D(n)是图的距离矩阵图的距离矩阵, , 同时引入一个后继点矩阵记录两点同时引入一个后继点矩阵记录两点间的最短路径间的最短路径. .1089 9是算法算法————算法步骤d(i,j) : i到j的距离;path(i,j): i到j的路径上i的后继点;输入带权邻接矩阵a(i,j).输入带权邻接矩阵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+程序（程序（算法）算法） [D,path,min1,path1]=floyd(a,start,) [D,path,min1,path1]=floyd(a,start,)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:nfor j=1:nfor j=1:nj jif D(i,j)~=infif D(i,j)~=(i,j)=j;path(i,j)=j;end, end, , end, k=1:nfor k=1:nfor i=1:nfor i=1:nfor j=1:nfor j=1:nif 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)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,, end, end,endif ==3if ==3min1=D(start,);min1=D(start,);((m(1)=start;m(1)=start;i=1;i=1;path1=[ ]; path1=[ ]; while path(m(i),)~= path(m(i),)~==i+1;k=i+1;m(k)=path(m(i),);m(k)=path(m(i),);i=i+1;i=i+1;d (i+1)=;m(i+1)=;path1=m;path1=m;end end ,,););最短路径算法最短路径算法算法程序的使用说明：算法程序的使用说明：1. [D, path]=floyd(a), 1. [D, path]=floyd(a), 返回矩阵图的带权邻接矩阵，图的带权邻接矩阵， D(i,j)path(i,j)path(i,j)表示表示i i与返回矩阵D, path D, path 。
其中D(i,j)表示表示i i到到j j的最短距离与j j之间的最短路径上顶点之间的最短路径上顶点i i的后继点。 其中a a是所求的最短距离; 的后继点. .是所求; 2. [D, path, min1, path1]= floyd(a,i,j) 2. [D, path, min1, path1]= floyd(a,i,j) 返回矩阵并返回并返回i i与与j j之间的最短距离之间的最短距离min1返回矩阵D, path; D, path; min1和最短路径和最短路径path1..edge= [ 2,3,1 ,3,3,5,4, 4,1 ,7,6,6,5, 5,1 1 , 1 ,8,6,9,1 0,8,9, 9,1 0;...edge= [ 2,3,1 ,3,3,5,4, 4,1 ,7,6,6,5, 5,1 1 , 1 ,8,6,9,1 0,8,9, 9,1 0;...引例引例１ １的的Ｍ ａ ｔｌａ ｂＭ ａ ｔｌａ ｂ求解求解3,4,2,7,5,3,5,1 1 ,7,6,7,5,6,1 1 , 5, 8,1 ,9,5,1 1 ,9,8,1 0,9;...3,4,2,7,5,3,5,1 1 ,7,6,7,5,6,1 1 , 5, 8,1 ,9,5,1 1 ,9,8,1 0,9;...3,5,8,5,6,6,1 ,1 2,7,9,9,2,2,1 0,1 0,8,8,3,7, 2, 9,9, 2, 2] ;3,5,8,5,6,6,1 ,1 2,7,9,9,2,2,1 0,1 0,8,8,3,7, 2, 9,9, 2, 2] ;n= 1 1 ; = inf ones(n, n) ;n= 1 1 ; = inf ones(n, n) ;for i= 1 :nfor i= 1 :(i, i) = 0;(i, i) = 0;13 35 61 15 58 87 79 93 33 32 27 77 i= 1 :size(edge,2)for i= 1 :size(edge,2)(edge(1 , i), edge(2, i)) = edge(3, i);(edge(1 , i), edge(2, i)) = edge(3, i);[ dis, path] = dij kstra(, 1 , 1 1 )[ dis, path] = dij kstra(, 1 , 1 1 )10982 28 89 92 2运行上页程序输出运行上页程序输出：引例引例１ １的求解的求解dis = =189 1 0 1 115因此顶点1 到顶点1 1 的最短路径为1 →8 →9 →1 0 →1 1 , 其长度为21 。
建立脚本建立脚本m m文件如下：文件如下：引例引例２ ２的的Ｍ ａ ｔｌａ ｂＭ ａ ｔｌａ ｂ求解求解a= [ 0,50,inf,40,25,1 0;50,0,1 5,20,inf,25;inf,1 5,0,1 0,20,inf;a= [ 0,50,inf,40,25,1 0;50,0,1 5,20,inf,25;inf,1 5,0,1 0,20,inf;……40,20,1 0,0,1 0,25;25,inf,20,1 0,0,55;1 0,25,inf,25,55,0] ;40,20,1 0,0,1 0,25;25,inf,20,1 0,0,55;1 0,25,inf,25,55,0] ;[D, path]=floyd(a)[D, path]=floyd(a)运行便可输出结果。运行便可输出结果。∞∞20 550∞∞∞∞运行输出结果：运行输出结果：D =D =0 35 45 35 25 1 00 35 45 35 25 1 0350 1 5 20 30 25350 1 5 20 30 2545 1 50 1 0 20 3545 1 50 1 0 20 20 1 00 1 0 2535 20 1 00 1 0 01 0001 01 5 ∞∞∞∞25 30 20 1 00 3525 30 20 1 00 351 0 25 35 25 3501 0 25 35 25 =path = 550∞∞D D便是最廉价的航费表，便是最廉价的航费表，要求飞行路线， 由要求飞行路线，由path阵可以得到阵可以得到阵可以得到数据结构最短路径ppt， 比如阵可以得到， 比如2 2到路线：路线： path(2,5)=4, path(2,5)=4, path(4,5)=5,path(4,5)=5,因此， 应为2→4 →52→4 →5path矩到5 5的到5 5的矩的的比如比如2 2到因此， 应为假设图有 n 个顶点， 现需要求从顶点1 到顶点n的最短路径.设决策变量为xij, 当顶点1 至顶点n的路上含弧(i,j ) 时， xij= 1 ； 否则xij= 0. 其数学规划表达式为最短路径问题的０－ １规划模型(( , )i j)min;ijiji jEE...
