用matlab实现寻找最短路
用matlab寻找赋权图中的最短路中的应用
1引言
图论是应用数学的一个分支，它的概念和结果来源都非常广泛，最早起源于一些数学游戏的难题研究，如欧拉所解决的格尼斯堡七桥问题，以及在民间广泛流传的一些游戏的难题，如迷宫问题，博弈问题等。这些古老的难题，吸引了很多学者的注意。
1847年，图论应用于分析电路网络，这是它最早应用于工程科学，以后随着科学的发展，图论在解决运筹学，网络理论，信息论，控制论，博弈论以及计算机科学等各个领域的问题时，发挥出很大的作用。在实践中，图论已成为解决自然科学，工程技术，社会科学，军事等领域中许多问题的有力工具之一。
最短路问题是图论理论中的经典问题，寻找最短路径就是在指定网络中两节点间找一条距离最小的路。
2 最短路
2.1 最短路的定义（short-path problem）
对最短路问题的研究早在上个世纪60年代以前就卓有成效了，其中对赋权图()0
w≥的有效算法是由荷兰著名计算机专家E.W.Dijkstra在1959年首次提出的,该算法能ij
够解决两指定点间的最短路,也可以求解图G中一特定点到其它各顶点的最短路。后来海斯在Dijkstra算法的基础之上提出了海斯算法。但这两种算法都不能解决含有负权的图的最短路问题。因此由Ford提出了Ford算法,它能有效地解决含有负权的最短路问题。但在现实生
w≥的情况下选择Dijkstra算法。活中,我们所遇到的问题大都不含负权,所以我们在()0
ij
若网络中的每条边都有一个数值(长度、成本、时间等)，则找出两节点(通常是源节点和阱节点)之间总权和最小的路径就是最短路问题。最短路问题是网络理论解决的典型问题之一，它不仅可以直接应用于解决生产实际的许多问题，如管路铺设、线路安装、厂区布局和设备更新等，而且经常被作为一个基本的工具，用于解决其他的做优化问题。
定义1：若图G=G（V，E）中个边[v i,v j]都赋有一个实数w ij ，则称这样的图G为赋权图，w ij 称为边[v i,v j]上的权。
定义2：给定一个赋权有向图，即给一个有向图D=（V,A），对每一个弧a=（v i,v j），相应地有权w（a）=w ij，又给定D中的两个顶点v s ，v t 。设P是D中从v s 到v t 的一条路，定义路P的权是P中所有弧的权之和，记为w（P）。最短路问题就是要在所有从v s到
min w（P）式中v t 的路中，求一条权最小的路，即求一条从v s到v t 的路P0 ，使w（P0）=
P
对D中所有从v s到v t 的路P最小，称P0 是从v s到v t 的最短路。
2.2最短路问题算法的基本思想及其基本步骤
在求解网络图上节点间最短路径的方法中，目前国内外一致公认的比较好的算法有Dijkstra和Floyd算法。这两种算法，网络被抽象为一个图论中定义的有向图或无向图，并利用图的节点邻接矩阵记录点的关联信息。在进行图的遍历搜索最短路径时，以该矩阵为基础
不断进行目标值的最小性判别，知道获得最后的优化路径。鉴于课本使用Dijkstra算法，下面用Floyd算法进行计算：
设A=（a）n*n 为赋权图G=（V，E，F）的矩阵，当V i V j ∈E时，a ij =F（v i，v j），否则，
取a
ij =0，a
ij
=+∞（i≠j），d ij 表示从v i到v j 的点的距离，r
ij
表示从v i到v j 的点的最短路中的
一个点的编号。
①赋初值。对所有i，j，d ij = a ij ，r ij =j，k=1，转向②；
②更新d ij ，r ij ，对所有i，j，若d ik + d kj < d ij ,则令d ij = d ik + d kj ，r ij =k，转向；
③终止判断。若d ij <0,则存在一条含有顶点v i的负回路，终止；或者k=n，终止；否则，
另k=k+1，转向②。
最短路线可由r ij得到。
2.3用matlab程序实现上述算法
编写程序函数程序如下：
function f=shortpath(n,A)
clear;
n=input('请输入矩阵的阶n=');
A=input('请输入赋权图对应的n阶矩阵A='); % 顶点之间不通时，用inf表示（MATLAB中，inf 表示无穷）
D=A; %赋初值
for(i=1:n)
for(j=1:n)
R(i,j)=j;
end;
end %赋路径初值
for(k=1:n)
for(i=1:n)
for(j=1:n)
if(D(i,k)+D(k,j) D(i,j)=D(i,k)+D(k,j); %更新dij R(i,j)=k; %更新rij end; end; end k %显示迭代步数 D %显示每步迭代后的路长 R %显示每步迭代后的路径 pd=0; for(i=1:n) %含有负权 if(D(i,j)<0) pd=1; break; end; end%存在一条含有顶点的vi的负回路 if(pd) break; end %存在一条负回路，终止程序 end%程序结束 下面用一个实际的例子进行一下函数实际运算： 例：求解下赋权图中任意两点中的最短路。 V1 6 V4 2 6 5 3 8 V08 V2 1 V5 6 v7 1 7 2 4 3 V39 V5 用matlab函数运行以后，运行结果如下： 请输入矩阵的阶n=8 请输入赋权图对应的n阶矩阵A=[0 2 8 1 inf inf inf inf;2 0 6 inf 1 inf inf inf;8 6 0 7 5 1 2 inf;1 inf 7 0 inf inf 9 inf;inf 1 5 inf 0 3 inf 8;inf inf 1 inf 3 0 4 6;inf inf 2 9 inf 4 0 3;inf inf inf inf 8 6 3 0] k =1 D = 0 2 8 1 Inf Inf Inf Inf 2 0 6 3 1 Inf Inf Inf 8 6 0 7 5 1 2 Inf 1 3 7 0 Inf Inf 9 Inf Inf 1 5 Inf 0 3 Inf 8 Inf Inf 1 Inf 3 0 4 6 Inf Inf 2 9 Inf 4 0 3 Inf Inf Inf Inf 8 6 3 0 R = 1 2 3 4 5 6 7 8 1 2 3 1 5 6 7 8 1 2 3 4 5 6 7 8 1 1 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 D = 0 2 8 1 3 Inf Inf Inf 2 0 6 3 1 Inf Inf Inf 8 6 0 7 5 1 2 Inf 1 3 7 0 4 Inf 9 Inf 3 1 5 4 0 3 Inf 8 Inf Inf 1 Inf 3 0 4 6 Inf Inf 2 9 Inf 4 0 3 Inf Inf Inf Inf 8 6 3 0 R = 1 2 3 4 2 6 7 8 1 2 3 1 5 6 7 8 1 2 3 4 5 6 7 8 1 1 3 4 2 6 7 8 2 2 3 2 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 k =3 D = 0 2 8 1 3 9 10 Inf 2 0 6 3 1 7 8 Inf 8 6 0 7 5 1 2 Inf 1 3 7 0 4 8 9 Inf 3 1 5 4 0 3 7 8 9 7 1 8 3 0 3 6 10 8 2 9 7 3 0 3 Inf Inf Inf Inf 8 6 3 0 R = 1 2 3 4 2 3 3 8 1 2 3 1 5 3 3 8 1 2 3 4 5 6 7 8 1 1 3 4 2 3 7 8 2 2 3 2 5 6 3 8 3 3 3 3 5 6 3 8 3 3 3 4 3 3 7 8 1 2 3 4 5 6 7 8 D = 0 2 8 1 3 9 10 Inf 2 0 6 3 1 7 8 Inf 8 6 0 7 5 1 2 Inf 1 3 7 0 4 8 9 Inf 3 1 5 4 0 3 7 8 9 7 1 8 3 0 3 6 10 8 2 9 7 3 0 3 Inf Inf Inf Inf 8 6 3 0 R = 1 2 3 4 2 3 3 8 1 2 3 1 5 3 3 8 1 2 3 4 5 6 7 8 1 1 3 4 2 3 7 8 2 2 3 2 5 6 3 8 3 3 3 3 5 6 3 8 3 3 3 4 3 3 7 8 1 2 3 4 5 6 7 8 k =5 D = 0 2 8 1 3 6 10 11 2 0 6 3 1 4 8 9 8 6 0 7 5 1 2 13 1 3 7 0 4 7 9 12 3 1 5 4 0 3 7 8 6 4 1 7 3 0 3 6 10 8 2 9 7 3 0 3 11 9 13 12 8 6 3 0 R = 1 2 3 4 2 5 3 5 1 2 3 1 5 5 3 5 1 2 3 4 5 6 7 5 1 1 3 4 2 5 7 5 2 2 3 2 5 6 3 8 5 5 3 5 5 6 3 8 3 3 3 4 3 3 7 8 5 5 5 5 5 6 7 8 D = 0 2 7 1 3 6 9 11 2 0 5 3 1 4 7 9 7 5 0 7 4 1 2 7 1 3 7 0 4 7 9 12 3 1 4 4 0 3 6 8 6 4 1 7 3 0 3 6 9 7 2 9 6 3 0 3 11 9 7 12 8 6 3 0 R = 1 2 6 4 2 5 6 5 1 2 6 1 5 5 6 5 6 6 3 4 6 6 7 6 1 1 3 4 2 5 7 5 2 2 6 2 5 6 6 8 5 5 3 5 5 6 3 8 6 6 3 4 6 3 7 8 5 5 6 5 5 6 7 8 k =7 D = 0 2 7 1 3 6 9 11 2 0 5 3 1 4 7 9 7 5 0 7 4 1 2 5 1 3 7 0 4 7 9 12 3 1 4 4 0 3 6 8 6 4 1 7 3 0 3 6 9 7 2 9 6 3 0 3 11 9 5 12 8 6 3 0 R = 1 2 6 4 2 5 6 5 1 2 6 1 5 5 6 5 6 6 3 4 6 6 7 7 1 1 3 4 2 5 7 5 2 2 6 2 5 6 6 8 5 5 3 5 5 6 3 8 6 6 3 4 6 3 7 8 5 5 7 5 5 6 7 8 D = 0 2 7 1 3 6 9 11 2 0 5 3 1 4 7 9 7 5 0 7 4 1 2 5 1 3 7 0 4 7 9 12 3 1 4 4 0 3 6 8 6 4 1 7 3 0 3 6 9 7 2 9 6 3 0 3 11 9 5 12 8 6 3 0 R = 1 2 6 4 2 5 6 5 1 2 6 1 5 5 6 5 6 6 3 4 6 6 7 7 1 1 3 4 2 5 7 5 2 2 6 2 5 6 6 8 5 5 3 5 5 6 3 8 6 6 3 4 6 3 7 8 5 5 7 5 5 6 7 8 注：上例中是用一个无向赋权图，对与有向赋权图只需要把反向的定义为无穷大（在matlab 中即用inf代替不能到达的情况），一样可以调用上述函数程序进行运算。 3 最短路的实际应用 ●最短路问题在交通网络结构的分析，交通运输路线（公路、铁路、河流航运线、航空线、管道运输路线等）的选择，通讯线路的建造与维护，运输货流的最小成本分析，城公共交通网络的规划等，都有直接应用的价值。 ●最短路问题在实际中还常用于汽车导航系统以及各种应急系统等（110报警、119火警以及120医疗救护系统），这些系统一般要求计算出到出事地点的最佳路线的时间最短。利用最短路还需要实际计算出前方的行驶路线，这就决定了最短路径问题的实现应该是高效率的。 ●根据现在发展的要求，在城乡一体化的总体思路中，为实现农村村村通的目标，针对农村地理分布，进行合理规划，对与优化农村交通网络，促进农村发展有重要的内容。 4 结语 本文将最短路理论与实际相联系，尤其是对与当前热点问题的应用，具有很重要的意义。将实际生活中出现的安全隐患尽量降低。同时也凸显出学习与应用最短路原理的重要性。要在平时的生活中，注意学习中的相关联系，那样会对学习产生更大的兴趣。 用matlab寻找赋权图中的最短路中的应用 1引言 图论是应用数学的一个分支，它的概念和结果来源都非常广泛，最早起源于一些数学游戏的难题研究，如欧拉所解决的格尼斯堡七桥问题，以及在民间广泛流传的一些游戏的难题，如迷宫问题，博弈问题等。这些古老的难题，吸引了很多学者的注意。 1847年，图论应用于分析电路网络，这是它最早应用于工程科学，以后随着科学的发展，图论在解决运筹学，网络理论，信息论，控制论，博弈论以及计算机科学等各个领域的问题时，发挥出很大的作用。在实践中，图论已成为解决自然科学，工程技术，社会科学，军事等领域中许多问题的有力工具之一。 最短路问题是图论理论中的经典问题，寻找最短路径就是在指定网络中两节点间找一条距离最小的路。 2 最短路 2.1 最短路的定义（short-path problem） 对最短路问题的研究早在上个世纪60年代以前就卓有成效了，其中对赋权图()0 w≥的有效算法是由荷兰著名计算机专家E.W.Dijkstra在1959年首次提出的,该算法ij 能够解决两指定点间的最短路,也可以求解图G中一特定点到其它各顶点的最短路。后来海斯在Dijkstra算法的基础之上提出了海斯算法。但这两种算法都不能解决含有负权的图的最短路问题。因此由Ford提出了Ford算法,它能有效地解决含有负权的最短路问题。但在 现实生活中,我们所遇到的问题大都不含负权,所以我们在()0ij w≥的情况下选择Dijkstra算法。 若网络中的每条边都有一个数值(长度、成本、时间等)，则找出两节点(通常是源 节点和阱节点)之间总权和最小的路径就是最短路问题。最短路问题是网络理论解决 的典型问题之一，它不仅可以直接应用于解决生产实际的许多问题，如管路铺设、线 路安装、厂区布局和设备更新等，而且经常被作为一个基本的工具，用于解决其他的 做优化问题。 定义1：若图G=G（V，E）中个边[v i ,v j]都赋有一个实数w ij ，则称这样的图G 为赋权图，w ij 称为边[v i ,v j]上的权。 定义2：给定一个赋权有向图，即给一个有向图D=（V,A），对每一个弧a=（v i ,v j），相应地有权w（a）=w ij，又给定D中的两个顶点v s ，v t 。设P是D中从v s 到v t 的一条路，定义路P的权是P中所有弧的权之和，记为w（P）。最短路问题就是要在所有从v s到v t 的路中，求一条权最小的路，即求一条从v s到v t 的路P0 ，使w（P0）= min w（P） P 式中对D中所有从v s到v t 的路P最小，称P0 是从v s到v t 的最短路。 2.2 最短路问题算法的基本思想及其基本步骤 在求解网络图上节点间最短路径的方法中，目前国内外一致公认的比较好的算法有Dijkstra和Floyd算法。这两种算法，网络被抽象为一个图论中定义的有向图或无向图，并利用图的节点邻接矩阵记录点的关联信息。在进行图的遍历搜索最短路径时，以该矩阵为基础不断进行目标值的最小性判别，知道获得最后的优化路径。鉴于课本使用Dijkstra算法，下面用Floyd算法进行计算： 设A=（a）n*n 为赋权图G=（V，E，F）的矩阵，当V i V j ∈E时，a ij =F（v i，v j），否则，取a ij =0，a ij =+∞（i≠j），d ij 表示从v i到v j 的点的距离，r ij 表示从v i到v j 的点的最短路中的一个点的编号。 ①赋初值。对所有i，j，d ij = a ij ，r ij =j，k=1，转向②； ②更新d ij ，r ij ，对所有i，j，若d ik + d kj < d ij ,则令d ij = d ik + d kj ，r ij =k，转向； ③终止判断。若d ij <0,则存在一条含有顶点v i的负回路，终止；或者k=n，终止；否则， 另k=k+1，转向②。 最短路线可由r ij得到。 最短路径法射线追踪的MATLAB 实现 李志辉 刘争平 （西南交通大学土木工程学院 成都 610031） 摘 要：本文探讨了在MA TLAB 环境中实现最短路径射线追踪的方法和步骤，并通过数值模拟演示了所编程序在射线追踪正演计算中的应用。 关键词：最短路径法 射线追踪 MATLAB 数值模拟 利用地震初至波确定近地表介质结构，在矿产资源的勘探开发及工程建设中有重要作用。地震射线追踪方法是研究地震波传播的有效工具，目前常用的方法主要有有限差分解程函方程法和最小路径法。最短路径方法起源于网络理论，首次由Nakanishi 和Yamaguchi 应用域地震射线追踪中。Moser 以及Klimes 和Kvasnicha 对最短路径方法进行了详细研究。通过科技人员的不断研究，最短路径方法目前已发展较为成熟，其基本算法的计算程序也较为固定。 被称作是第四代计算机语言的MA TLAB 语言，利用其丰富的函数资源把编程人员从繁琐的程序代码中解放出来。MA TLAB 用更直观的、符合人们思维习惯的代码，为用户提供了直观、简洁的程序开发环境。本文介绍运用Matlab 实现最短路径法的方法和步骤，便于科研院校教学中讲授、演示和理解最短路径方法及其应用。 1 最短路径法射线追踪方法原理 最短路径法的基础是Fermat 原理及图论中的最短路径理论。其基本思路是，对实际介质进行离散化，将这个介质剖分成一系列小单元，在单元边界上设置若干节点，并将彼此向量的节点相连构成一个网络。网络中，速度场分布在离散的节点上。相邻节点之间的旅行时为他们之间欧氏距离与其平均慢度之积。将波阵面看成式由有限个离散点次级源组成，对于某个次级源（即某个网格节点），选取与其所有相邻的点（邻域点）组成计算网格点；由一个源点出发，计算出从源点到计算网格点的透射走时、射线路径、和射线长度；然后把除震源之外的所有网格点相继当作次级源，选取该节点相应的计算网格点，计算出从次级源点到计算网格点的透射走时、射线路径、和射线长度；将每次计算出来的走时加上从震源到次级源的走时，作为震源点到该网格节点的走时，记录下相应的射线路径位置及射线长度。 图1 离散化模型（星点表示震源或次级震源，空心点为对应计算网格点） 根据Fermat 原理逐步计算最小走时及射线方向。设Ω为已知走时点q 的集合，p 为与其相邻的未知走时点，tq 分别和p 点的最小走时，tqp 为q 至p 最小走时。r 为p 的次级源位置，则 )}(min :{qp q P t t t q r q +==Ω ∈ 根据Huygens 原理，q 只需遍历Q 的边界（即波前点），当所有波前邻点的最小走时都求出时，这些点又成为新的波前点。应用网络理论中的最短路径算法，可以同时求出从震源点传至所有节点之间的连线近似地震射线路径。 2 最短路径法射线追踪基本算法步骤 把网格上的所有节点分成集合p 和q ，p 为已知最小旅行时的结点总数集合，q 为未知最小旅行时的节点的集合。若节点总数为n ，经过n 次迭代后可为求出所有节点的最小旅行时。过程如下： 1) 初始时 q 集合包含所有节点，除震源s 的旅行时已知为ts ＝0外，其余所有节点的旅行时均为ti ＝（i 属于Q 但不 等于s ）。P 集合为空集。 2) 在Q 中找一个旅行时最小的节点i ，它的旅行时为ti ； 3) 确定与节点i 相连的所有节点的集合V ； 4) 求节点j （j 属于V 且j 不属于P ）与节点i 连线的旅行时dtij ； 5) 求节点j （）的新旅行时tj （取原有旅行时tj 与tj ＋dtij 的最小值）； 6) 将i 点从Q 集合转到P 集合； 7) 若P 集合中的节点个数小于总节点数N ，转2，否则结束旅行时追踪； 8) 从接收点开始倒推出各道从源点道接收点的射线路径，只要每个节点记下使它形成最小旅行时的前一个节点号， 用matlab寻找赋权图中的最短路 专业： 小组：第22小组 小组成员： 课题：用matlab寻找赋权图中的最短路 采用形式：集体讨论，并到图书馆搜集相关资料，进行编程，运行。最后以论文的形式表现出来。 1引言 图论是应用数学的一个分支，它的概念和结果来源都非常广泛，最早起源于一些数学游戏的难题研究，如欧拉所解决的格尼斯堡七桥问题，以及在民间广泛流传的一些游戏的难题，如迷宫问题，博弈问题等。这些古老的难题，吸引了很多学者的注意。 1847年，图论应用于分析电路网络，这是它最早应用于工程科学，以后随着科学的发展，图论在解决运筹学，网络理论，信息论，控制论，博弈论以及计算机科学等各个领域的问题时，发挥出很大的作用。在实践中，图论已成为解决自然科学，工程技术，社会科学，军事等领域中许多问题的有力工具之一。 最短路问题是图论理论中的经典问题，寻找最短路径就是在指定网络中两节点间找一条距离最小的路。 2 最短路 2.1 最短路的定义（short-path problem） 对最短路问题的研究早在上个世纪60年代以前就卓有成效了， 若网络中的每条边都有一个数值(长度、成本、时间等)，则找出两节点(通常是源节点和阱节点)之间总权和最小的路径就是最短路问题。最短路问题是网络理论解决的典型问题之一，它不仅可以直接应用于解决生产实际的许多问题，如管路铺设、线路安装、厂区布局和设备更新等，而且经常被作为一个基本的工具，用于解决其他的做优化问题。 定义1：若图G=G（V，E）中个边[v i,v j]都赋有一个实数w ij ，则称这样的图G为赋权图，w ij 称为边[v i,v j]上的权。 定义2：给定一个赋权有向图，即给一个有向图D=（V,A），对每一个弧a=（v i,v j），相应地有权w（a）=w ij，又给定D中的两个顶点v s ，v t 。设P是D中从v s 到v t 的一条路，定义路P的权是P中所有弧的权之和，记为w（P）。最短路问题就是要在所有从v s到v t 的路中，求一条权最小的路，即求一条从v s min w（P）式中对D中所有从v s到v t 的路P最小，到v t 的路P0 ，使w（P0）= P 称P0 是从v s到v t 的最短路。 2.2最短路问题算法的基本思想及其基本步骤 在求解网络图上节点间最短路径的方法中，目前国内外一致公认的比较好的算法有Dijkstra和Floyd算法。这两种算法，网络被抽象为一个图论中定义的有向图或无向图，并利用图的节点邻接矩阵记录点的关联信息。在进行图的遍历搜 默认是Dijkstra 算法 是有权的, 我想如果把权都赋1的话, 就相当于没权的了 参数是带权的稀疏矩阵及结点 看看这两个例子(一个有向一个无向), 或许你能找到你想知道的 % Create a directed graph with 6 nodes and 11 edges W = [.41 .99 .51 .32 .15 .45 .38 .32 .36 .29 .21]; %这是权 DG = sparse([6 1 2 2 3 4 4 5 5 6 1],[2 6 3 5 4 1 6 3 4 3 5],W) %有权的有向图 h = view(biograph(DG,[],'ShowWeights','on')) %画图, 这个好玩 % Find shortest path from 1 to 6 [dist,path,pred] = graphshortestpath(DG,1,6) %找顶点1到6的最短路径 % Mark the nodes and edges of the shortest path set(h.Nodes(path),'Color',[1 0.4 0.4]) %上色 edges = getedgesbynodeid(h,get(h.Nodes(path),'ID')); set(edges,'LineColor',[1 0 0]) %上色 set(edges,'LineWidth',1.5) %上色 下面是无向图的例子 % % Solving the previous problem for an undirected graph % UG = tril(DG + DG') % h = view(biograph(UG,[],'ShowArrows','off','ShowWeights','on')) % % Find the shortest path between node 1 and 6 % [dist,path,pred] = graphshortestpath(UG,1,6,'directed',false) % % Mark the nodes and edges of the shortest path % set(h.Nodes(path),'Color',[1 0.4 0.4]) % fowEdges = getedgesbynodeid(h,get(h.Nodes(path),'ID')); % revEdges = getedgesbynodeid(h,get(h.Nodes(fliplr(path)),'ID')); % edges = [fowEdges;revEdges]; % set(edges,'LineColor',[1 0 0]) % set(edges,'LineWidth',1.5) clc;close all; clear; load data; % global quyu; quyu = [2,3];%一片区域 z_jl = lxjl(jdxx,lxxh);%计算路线的距离 z = qyxz(jdxx,quyu,z_jl); % 根据节点信息，从z中将y区域的节点和路线选出所有点的信息 hzlx(z); %绘制Z的图像 基于MATLAB求解最短路问题 1.引言 MATLAB和Mathematica、Maple并称为三大数学软件。它在数学类科技应用软件中在数值计算方面首屈一指。通过本学期的学习了解和上机实践，已经初步掌握使用MATLAB工具解决实际问题的能力。结合运筹学课程的学习，我考虑使用MATLAB求解最短路问题，而在所有求解最短路的方法中，Dijkstra算法是最为经典的一种，因此本文主要解决在MATLAB环境下使用Dijkstra算法求解最短路。 1.1 提出问题 设6个城市v1,v2,......,v6之间的一个公路网(图1)每条公路为图中的边,边上的权数表示该段公路的长度(单位:百公里),设你处在城市v1,那么从v1到v6应选择哪一路径使你的费用最省。 1.2 分析问题 这属于一个典型的求解最短路的问题，图中顶点代表六个城市，边上的权数表示该段公路的长度，题目所求为从v1到v6、的一条费用最省的路径，我们假设所需费用仅与路径长短有关，因此求费用最省的路径即求权值最小的路径。网络图中各权值均为正，可以使用Dijkstra算法。 1.3 数据整理 将网络图中各边的权作如下整理以方便程序运行 W(1,2)=5; W(2,1)=5; W(1,3)=2; W(3,1)=2; W(2,3)=1; W(3,2)=1; W(2,4)=5; W(4,2)=5; W(2,5)=5; W(5,2)=5; W(3,4)=8; W(4,3)=8; W(3,5)=10; W(5,3)=10; W(4,5)=2; W(5,4)=2; W(4,6)=5; W(6,4)=5; W(5,6)=2; W(6,5)=2; 2.数学原理 2.1 Dijkstra算法介绍 Dijkstra 算法思想为：设G=（V，E）是一个带权有向图（也可以是无向图，无向图是有向图的特例），把图中顶点集合V分成两组：第一组为已求出最短路径的顶点集合（用S 表示，初始时S 中只有一个源点，以后每求得一条最短路径，就将其加入到集合S 中，直到全部顶点都加入到S 中，算法就结束了）；第二组为其余未确定最短路径的顶点集合（用U 表示），按最短路径长度的递增次序依次把第二组的顶点加入S 中。在加入的过程中，总保持从源点v 到S 中各顶点的最短路径长度不大于从源点v 到U 中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S 中的顶点的距离就是从v 到此顶点的最短路径长度，U中的顶点的距离，是从v 到此顶点只包括S 中的顶点为中间顶点的当前最短路径长度。其步骤主要有： 第一，初始时，S 只包含源点，即S＝{顶点}，v 的距离为0。U 包含除v 外的其他顶点，U 中顶点u 距离为边上的权（若v 与u 有边）或（若u 不是v 的出边邻接点）。 第二，从U 中选取一个距离v 最小的顶点k，把k 加入S 中（该选定的距离就是v 到k 的最短路径长度）。 第三，以k 为新考虑的中间点，修改U 中各顶点的距离；若从源点v 到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u 的 最短路径问题m a t l a b 求解详尽版 Document serial number【UU89WT-UU98YT-UU8CB-UUUT-UUT108】 MATLAB 求最短路径 利用graphshortestpath 可以求最短路径，具体用法参考MATLAB帮助Examples： S=[1 1 2 2 3 3 4 4 4 4 5 6 6 7 8]; %起始节点向量 E=[2 3 5 4 4 6 5 7 8 6 7 8 9 9 9]; %终止节点向量 W=[1 2 12 6 3 4 4 15 7 2 7 7 15 3 10]; %边权值向量，有向图， G(9,9)=0; 9个节点 G=sparse(S,E,W); %关联矩阵的稀疏矩阵表示 G(9,9)=0; P=biograph(G,[],'ShowWeights','on');%建立有向图对象P H=view(P);%显示各个路径权值 [Dist,Path]=graphshortestpath(G,1,9,'Method','Dijkstra') %求节点1到节点9的最短路径 set(Path),'Color',[1 ]);%以下三条语句用红色修饰最短路径edges=getedgesbynodeid(H,get(Path),'ID')); set(edges,'LineColor',[1 0 0]); set(edges,'LineWidth',; %以下是运行结果，节点1到节点9的最短路径为19 Dist = 19 Path = 1 3 4 5 7 9 利用graphallshortestpaths可以求出所有最短路径Dists=graphallshortestpaths(G) %求所有最短路径Dists = 0 1 2 5 9 6 16 12 19 Inf 0 Inf 6 10 8 17 13 20 Inf Inf 0 3 7 4 14 10 17 Inf Inf Inf 0 4 2 11 7 14 Inf Inf Inf Inf 0 Inf 7 Inf 10 Inf Inf Inf Inf Inf 0 Inf 7 15 Inf Inf Inf Inf Inf Inf 0 Inf 3 Inf Inf Inf Inf Inf Inf Inf 0 10 两个指定顶点之间的最短路径 问题如下：给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线。 以各城镇为图G 的顶点，两城镇间的直通铁路为图G 相应两顶点间的边，得图G 。对G 的每一边e ，赋以一个实数)(e w —直通铁路的长度，称为e 的权，得到赋权图G 。G 的子图的权是指子图的各边的权和。问题就是求赋权图G 中指定的两个顶点00,v u 间的具最小权的轨。这条轨叫做00,v u 间的最短路，它的权叫做00,v u 间的距离，亦记作),(00v u d 。 求最短路已有成熟的算法：迪克斯特拉（Dijkstra ）算法，其基本思想是按距0u 从近到远为顺序，依次求得0u 到G 的各顶点的最短路和距离，直至0v （或直至G 的所有顶点），算法结束。为避免重复并保留每一步的计算信息，采用了标号算法。下面是该算法。 (i) 令0)(0=u l ，对0u v ≠，令∞=)(v l ，}{00u S =，0=i 。 (ii) 对每个i S v ∈（i i S V S \=），用 )}()(),({min uv w u l v l i S u +∈ 代替)(v l 。计算)}({min v l i S v ∈，把达到这个最小值的一个顶点记为1+i u ，令}{11++=i i i u S S 。 (iii). 若1||-=V i ，停止；若1||- MATLAB 求最短路径 利用graphshortestpath 可以求最短路径，具体用法参考MATLAB帮助Examples： S=[1 1 2 2 3 3 4 4 4 4 5 6 6 7 8]; %起始节点向量 E=[2 3 5 4 4 6 5 7 8 6 7 8 9 9 9]; %终止节点向量 W=[1 2 12 6 3 4 4 15 7 2 7 7 15 3 10]; %边权值向量，有向图，G(9,9)=0; 9个节点 G=sparse(S,E,W); %关联矩阵的稀疏矩阵表示 G(9,9)=0; P=biograph(G,[],'ShowWeights','on');%建立有向图对象P H=view(P);%显示各个路径权值 [Dist,Path]=graphshortestpath(G,1,9,'Method','Dijkstra') %求节点1到节点9的最短路径 set(H.Nodes(Path),'Color',[1 0.4 0.4]);%以下三条语句用红色修饰最短路径edges=getedgesbynodeid(H,get(H.Nodes(Path),'ID')); set(edges,'LineColor',[1 0 0]); set(edges,'LineWidth',2.0); %以下是运行结果，节点1到节点9的最短路径为19 Dist = 19 Path = 1 3 4 5 7 9 利用graphallshortestpaths可以求出所有最短路径Dists=graphallshortestpaths(G) %求所有最短路径Dists = 0 1 2 5 9 6 16 12 19 Inf 0 Inf 6 10 8 17 13 20 Inf Inf 0 3 7 4 14 10 17 Inf Inf Inf 0 4 2 11 7 14 Inf Inf Inf Inf 0 Inf 7 Inf 10 Inf Inf Inf Inf Inf 0 Inf 7 15 Inf Inf Inf Inf Inf Inf 0 Inf 3 Inf Inf Inf Inf Inf Inf Inf 0 10 Inf Inf Inf Inf Inf Inf Inf Inf 0 最短路法MATLAB 程序 例1： 某公司在六个城市621,,,c c c 中有分公司，从i c 到j c 的直接航程票价记在下述矩阵的),(j i 位置上。（∞表示无直接航路），请帮助该公司设计一张城市1c 到其它城市间的票价最便宜的路线图。 ??????????????????∞∞∞∞∞∞ 05525251055010202525100102040 2010015252015050102540500 用矩阵n n a ?（n 为顶点个数）存放各边权的邻接矩阵，行向量pb 、1index 、 2index 、d 分别用来存放P 标号信息、标号顶点顺序、标号顶点索引、最短通路的值。其中分量 ? ??=顶点未标号当第顶点已标号当第i i i pb 01)(； )(2i index 存放始点到第i 点最短通路中第i 顶点前一顶点的序号； )(i d 存放由始点到第i 点最短通路的值。 求第一个城市到其它城市的最短路径的Matlab 程序如下： 程序一： clc,clear a=zeros(6); %邻接矩阵初始化 a(1,2)=50;a(1,4)=40;a(1,5)=25;a(1,6)=10; a(2,3)=15;a(2,4)=20;a(2,6)=25; a(3,4)=10;a(3,5)=20; a(4,5)=10;a(4,6)=25; a(5,6)=55; a=a+a'; %将矩阵数据对称赋予矩阵 a(find(a==0))=inf; %找到0值并赋值为inf pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a)); d(1:length(a))=inf;d(1)=0; temp=1; %最新的P标号的顶点 while sum(pb) 湖南大学 MATLAB实训报告 题目：matlab计算最短路径问题 学院名称：信息科学与工程学院 专业班级：软件工程四班 学生姓名：彭天越 学号： 20112601416 日期：2013年7月3号 目录 题目 (2) 问题描述 (3) （1）根据无向图A，使用Di.jistra算法 (3) （2）根据有向图B，使用Warshall-Floyd算法 (4) 思路及代码 (4) （1）思路 (4) （2）源代码 (5) 测试结果说明 (10) (1)Di.jistra算法 (10) (2)Floyd算法 (11) 小结 (11) 题目 求下图中顶点ν1到顶点ν11的最短距离和最短路（2学分） B.有向图 问题描述 (1)根据无向图A，使用Di.jistra算法 (2)根据有向图B，使用Warshall-Floyd算法 思路及代码 (1)思路 （1）Dijkstra算法 使用范围: 1)寻求从一固定顶点到其余各点的最短路径; 2)有向图、无向图和混合图; 3)权非负. 算法思路： 采用标号作业法,每次迭代产生一个永久标号, 从而生长一颗以v 为根的最短路树,在这颗树上每个顶点与根节点之间的路径皆为最短路径. 诉法步骤： S: 具有永久标号的顶点集; l(v): v的标记; f(v):v的父顶点,用以确定最短路径; 输入加权图的带权邻接矩阵w=[w(v i ,v j )] nxm . 1)初始化令l(v 0)=0,S=Φ;? v≠v ,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中为止. （2）Floyd算法 使用范围: 1)求每对顶点的最短路径; 2)有向图、无向图和混合图; MATLAB 最短路-标号法代码函数代码 function [min,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, end s(1)=start; u=start; while length(s) end path(i)=start; L=length(path); path=path(L:-1:1); 脚本代码 weight=[ 0 3 5 inf inf inf inf; 3 0 inf 2 inf inf inf ; 5 inf 0 1.5 4 inf inf; inf 2 1.5 0 inf 3 inf; inf inf 4 inf 0 0.5 3; inf inf inf 3 0.5 0 1.5; inf inf inf inf 3 1.5 inf; ]; [dis, path]=dijkstra(weight, i,j) 输出结果 >> weight=[ 0 3 5 inf inf inf inf; 3 0 inf 2 inf inf inf ; 5 inf 0 1.5 4 inf inf; inf 2 1.5 0 inf 3 inf; inf inf 4 inf 0 0.5 3; inf inf inf 3 0.5 0 1.5; inf inf inf inf 3 1.5 inf; ]; [dis, path]=dijkstra(weight,1,4) dis = 5 path = 1 2 4 >> weight=[ 0 3 5 inf inf inf inf; 3 0 inf 2 inf inf inf ; 5 inf 0 1.5 4 inf inf; inf 2 1.5 0 inf 3 inf; inf inf 4 inf 0 0.5 3; inf inf inf 3 0.5 0 1.5; inf inf inf inf 3 1.5 inf; ]; [dis, path]=dijkstra(weight,1,5) dis = 8.5000 path = 1 2 4 6 5 >> weight=[ 0 3 5 inf inf inf inf; 3 0 inf 2 inf inf inf ; 5 inf 0 1.5 4 inf inf; inf 2 1.5 0 inf 3 inf; inf inf 4 inf 0 0.5 3; inf inf inf 3 0.5 0 1.5; inf inf inf inf 3 1.5 inf; ]; [dis, path]=dijkstra(weight,1,7) dis = 9.5000 path = 1 2 4 6 7 Floyd最短路算法的MATLAB程序 2006-08-17 20:14 %floyd.m %采用floyd算法计算图a中每对顶点最短路 %d是矩离矩阵 %r是路由矩阵 function [d,r]=floyd(a) n=size(a,1); d=a; for i=1:n for j=1:n r(i,j)=j; end end r for k=1:n for i=1:n for j=1:n if d(i,k)+d(k,j) { double min=INF; int u=v0; for(int j=0;j 数学建模常用Matlab/Lingo/c代码总结系列——floyd最短路径 分类：Matlab数学建模2011-11-16 23:37 186人阅读评论(0) 收藏举报例9 某公司在六个城市c1,c2, …c6 中有分公司，从i ci 到cj的直接航程票价记在下述矩阵的(I,j) 位置上。（∞表示无直接航路），请帮助该公司设计一张城市c1 到其它城市间的票价最便宜的路线图。 [plain]view plaincopyprint? 1. clc,clear 2. 3. a=zeros(6); 4. 5. a(1,2)=50;a(1,4)=40;a(1,5)=25;a(1,6)=10; 6. 7. a(2,3)=15;a(2,4)=20;a(2,6)=25; 8. 9. a(3,4)=10;a(3,5)=20; 10. 11. a(4,5)=10;a(4,6)=25; 12. 13. a(5,6)=55; 14. 15. a=a+a'; 16. 17. a(find(a==0))=inf; 18. 19. p b(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a)); 20. 21. d(1:length(a))=inf;d(1)=0;temp=1; 22. 23. w hile sum(pb)用matlab实现寻找最短路
最短路径法射线追踪的MATLAB实现
用matlab寻找赋权图中的最短路
MATLAB解决最短路径问题代码
基于MATLAB求解最短路问题
最短路径问题matlab求解详尽版
最短路径的Dijkstra算法及Matlab程序
最短路径问题matlab求解详尽版
图论最短路MATLAB程序
matlab计算最短路径
metlab最短路标号法代码及结果
Floyd最短路算法的MATLAB程序
Matlab代码-佛洛依德最短路径
- Matlab基础：最短路径问题
- 基于MATLAB求解最短路问题
- 任意城市间最短路的Matlab语言实现
- MATLAB编程：最短路问题
- 用matlab实现寻找最短路
- matlab最短路径算法
- 最短路径问题matlab求解详尽版
- 中国数学建模-数学工具-Floyd最短路算法的MATLAB程序
- 用matlab寻找赋权图中的最短路
- 最短路径问题matlab求解详尽版
- 最短路算法,matlab程序
- Dijkstra最短路算法通用Matlab程序
- MATLAB解决最短路径问题代码
- 最短路径 Floyd算法 matlab实现
- Floyd最短路算法的MATLAB程序
- Matlab代码-佛洛依德最短路径
- matlab最短路径
- 基于MATLAB求解最短路问题
- matlab计算最短路径
- Dijkstra最短路算法通用Matlab程序