网站建设 功能需求,网站解析怎么做,企业网站带后台模板,100个免费网页设计模板摘要:为研究两地点之间距离#xff08;或耗时#xff09;最短路线规划#xff0c;采用MATLAB编程的方法来实现#xff0c;并利用Floyd算法记录距离#xff08;或耗时#xff09;最短路线。在不考虑各种影响因素的情况下#xff0c;以随机小样本数据为例进行演示#xf…摘要:为研究两地点之间距离或耗时最短路线规划采用MATLAB编程的方法来实现并利用Floyd算法记录距离或耗时最短路线。在不考虑各种影响因素的情况下以随机小样本数据为例进行演示求得由起点到目的地的最短耗时路径和耗时时长。 #1. 经典Dijkstra算法的基本思想及数学模型 ##1.1 基本思想 Dijkstra算法的基本思想是从某一点Vs开始依次向外探寻最短路径。过程中对于每一个点都要记下一个相应的数(即该点的标号)若此数表示从起点Vs到该点的最短路径的权值则用P标号反之表示从起点Vs到该点的最短路径的权值上界即用T标号算法的每一步就是修改T标号的点为P标号的点使赋权有向图D中的点全部转化为P标号的点至多经过p-1步方可求出从起点Vs到终点的最短路径。 ##1.2 代码
function mydijkstra(A,sb,db)
%A(输入量)表示邻接矩阵,sb—起点的标号,db—终点的标号
%B(输出量)表示所求最短耗时时长矩阵,dist—最短路的耗时时长, mypath—最短路的路径
mlength(A
for i2:mfor j1:(i-1)A(i,j)A(j,i);end
end
aA;
for k1:(m-1)b[1:(k-1),(k1):m];kklength(b);a_idk;b1[(k1):m];kk1length(b1);while kk0for j1:kk1teA(k,a_id)A(a_id,b1(j));if teA(k,b1(j))A(k,b1(j))te;endendmiid1;for j2:kkif A(k,b(j))A(k,b(miid))miidj;endenda_idb(miid);b[b(1:(miid-1)),b((miid1:kk))];kklength(b);if a_idkmiid1find(b1a_id);b1[b1(1:(miid1-1)),b1((miid11):kk1)];kk1length(b1);endendfor j(k1):mA(j,k)A(k,j);endendmsize(a,1);
pathzeros(m);for k1:mfor i1:mfor j1:mif a(i,j)a(i,k)a(k,j)a(i,j)a(i,k)a(k,j);path(i,j)k;endendendenddista(sb,db);parentpath(sb,:);%从起点sb到终点db的最短路上各顶点的前驱顶点parent(parent0)sb;%path中的分量为0表示该顶点的前驱是起点mypathdb; tdb;while t~sbpparent(t); mypath[p,mypath];tp;endfprintf(最短路距离矩阵:B\n);BA,dist,mypath#2.案例——两地点之间自主驾驶最省时路线选择 ##2. 1绘制公路网络拓扑结构 为了研究两地点之间自主驾驶最省时路线随机编写时间长度如表1所示并绘制出由点和边组成的公路网络静态拓扑结构如图1所示。图中节点V1为出发点所在地设定节数量为6并计算由V1到V6的最短耗时和最短耗时路径。 ##2.2 Dijkstra算法的MATLAB实现结果
Dijkstra 算法的MATLAB实现根据上文绘制的公路网络静态拓扑结构关系以及图中所标的道路实际耗时长度运用MATLAB 编程软件来实现Dijkstra最短路径算法并利用Floyd算法记录最短耗时线路。由软件可求得由V1到任意一点的最短耗时路径和耗时时长如表2所示。 在天气、路况等各种因素的影响下从V1到V6点的最省时路线为V1V3V6时间为16分钟具体如图2所示。
参考文献 [1] 曾庆福,王孟平.基于MATLAB编程Dijkstra算法的消防救援最佳路线研究[J].武警学院学报,2018,34(06):9-13. [2] 曹旭. 旅游线路优化设计研究[D]. 西北民族大学, 2012.
