MATLAB轻松绘制地图路线-Dijkstra(迪杰斯特拉)算法最短路径规划

## 1. 地图绘制 利用MATLAB绘制地图需要三个基本数据： 1. 节点 2. 节点坐标 <img src = "https://img-blog.csdnimg.cn/400b4060e7644fee8fc2e0cda8685447.png#pic_center" width=150> 3. 节点间相通的路线 <img src = "https://img-blog.csdnimg.cn/68d034c73c6c4ef491b7f468631949e6.png#pic_center" width=150> 以11B交通巡警平台调度问题中的A区数据为例： （数据及工程文件下载链接见文末） **Demo1：** ```python clc,clear,close all load zones_xy_data.mat load data2_stripped.mat %第一问封锁路口标号 load data2_A.mat load data4_A.mat x_1 = [xy_data(:,1),xy_data(:,2),xy_data(:,3)]; %全市交通路口节点标号，x坐标，y坐标 x_2 = [data2_A(:,1),data2_A(:,2)]; %A区交通路口的路线 x_3 = data4_A(:,1); %A区出入口 xx = zeros(582,1); xy = zeros(582,1); for i=1:92 xx(i)=x_1(i,2); xy(i)=x_1(i,3); %描点 hold on if i<=20 %A区防疫点 plot(xx(i),xy(i),'^m','markerface','g','markersize',20) if ismember(i,x_3) plot(xx(i),xy(i),'.r','markerface','r','markersize',23) %A区出入口 end elseif ismember(i,x_3) %A区出入口 plot(xx(i),xy(i),'.r','markerface','r','markersize',23) else plot(xx(i),xy(i),'.','Color','#6495ED','markersize',20) end text(xx(i),xy(i),num2str(x_1(i,1)),'color',[0 0 0],'fontsize',10); text(300,320,'A','Color','#6495ED','fontsize',25); end for j=1:length(data2_A(:,1)) %路线连接 dotx=[xx(x_2(j,1)), xx(x_2(j,2))]; doty=[xy(x_2(j,1)), xy(x_2(j,2))]; plot(dotx, doty,'-','Color','#6495ED','Linewidth',1.2) end ```  ## 2. 计算各节点之间的距离 可通过已知节点的坐标，计算出各节点之间的距离，有Matlab基础的同学可以尝试Demo2， 也可通过Excel自行实现； **Demo2:** ```python clc,clear,close all load zones_xy_data.mat load data2_A.mat load data2_stripped.mat x_1 = [xy_data(1:92,1),xy_data(1:92,2),xy_data(1:92,3)]; %A区节点标号，x坐标，y坐标 dist_A = [data2_A(:,1),zeros(140,2),data2_A(:,2),zeros(140,3)]; %计算距离矩阵 for i = 1:140 dist_A(i,2) = x_1(dist_A(i,1),2); %x坐标 dist_A(i,3) = x_1(dist_A(i,1),3); %y坐标 dist_A(i,5) = x_1(dist_A(i,4),2); %x坐标 dist_A(i,6) = x_1(dist_A(i,4),3); %y坐标 dist_A(i,7) = sqrt((dist_A(i,2)-dist_A(i,5))^2+(dist_A(i,3)-dist_A(i,6))^2); end save dist_A dist_A ``` 计算结果： <img src = "https://img-blog.csdnimg.cn/446f6e48ddf940a7a3829b7ae9dbfbf4.png#pic_center" width=350> ## 3. Dijkstra(迪杰斯特拉)算法 > 迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959年提出的，是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。 <img src = "https://img-blog.csdnimg.cn/5de0a0dc265e4805b57964d76288182a.png" width=150> 有向图：描述节点与节点间的路线与距离 <img src = "https://img-blog.csdnimg.cn/ea2d16a3b4274ba28bb084545d4c5388.png#pic_center" width=300> 简单例子：求以下有权图中节点1-6的最短路径与距离（工程附件中的route123.m）  ```python clc,clear,close all; n=6; %设置邻接矩阵大小 temp=1; %设置起点 %构建邻接矩阵 lines = zeros(6,6); lines(1,2)=3;lines(2,1)=3;lines(1,3)=6;lines(3,1)=6; lines(2,3)=2;lines(3,2)=2;lines(2,4)=7;lines(4,2)=7; lines(2,5)=5;lines(5,2)=5;lines(3,5)=5;lines(5,3)=5; lines(3,4)=2;lines(4,3)=2;lines(4,5)=1;lines(5,4)=1; lines(4,6)=4;lines(6,4)=4;lines(5,6)=8;lines(6,5)=8; %绘制图节点和边 G = digraph(lines); [path1,d1] = shortestpath(G,1,6,'Method','positive'); p = plot(G,'Linewidth',3); hold on highlight(p,path1,'EdgeColor','m') ``` 结果： ```bash path1 = 1 2 3 4 6 d1 = 11 ``` 实现步骤： 1. 构建邻接矩阵 假设现在有27个节点，每个节点间的距离为1，全连接则有27*27种可能的路线，构建一个27x27的矩阵存放这些点与点之间的距离。将所有通路作为矩阵中的一个元素，则构建出以下数据： ```bash %% Dijkstra算法求目标下最优路径 n=27; %设置邻接矩阵大小 temp=1; %设置起点 %定义邻接矩阵lines lines = zeros(27); lines(1,2)=1; lines(1,25)=1; lines(2,1)=1; lines(2,3)=1; lines(3,4)=1; lines(3,25)=1; lines(4,3)=1; lines(4,25)=1; lines(5,4)=1; lines(5,24)=1; lines(6,5)=1; lines(6,24)=1; lines(6,23)=1; lines(7,6)=1; lines(7,22)=1; lines(7,8)=1; lines(8,7)=1; lines(8,9)=1; lines(8,22)=1; lines(9,8)=1; lines(9,22)=1; lines(9,10)=1; lines(9,15)=1; lines(9,16)=1; lines(9,17)=1; lines(9,21)=1; lines(9,22)=1; lines(10,9)=1; lines(10,15)=1; lines(10,11)=1; lines(10,13)=1; lines(11,10)=1; lines(11,13)=1; lines(11,12)=1; lines(12,11)=1; lines(12,13)=1; lines(12,14)=1; lines(13,10)=1; lines(13,11)=1; lines(13,15)=1; lines(13,12)=1; lines(14,13)=1; lines(14,15)=1; lines(14,12)=1; lines(14,16)=1; lines(15,9)=1; lines(15,10)=1; lines(23,26)=1; lines(15,13)=1; lines(15,14)=1; lines(15,16)=1; lines(16,9)=1; lines(16,15)=1; lines(16,14)=1; lines(16,17)=1; lines(16,18)=1; lines(17,9)=1; lines(17,18)=1; lines(17,16)=1; lines(17,21)=1; lines(18,17)=1; lines(18,16)=1; lines(18,20)=1; lines(18,19)=1; lines(19,18)=1; lines(19,20)=1; lines(20,19)=1; lines(20,18)=1; lines(20,21)=1; lines(21,20)=1; lines(21,9)=1; lines(21,22)=1; lines(21,23)=1; lines(21,27)=1; lines(21,17)=1; lines(22,23)=1; lines(22,6)=1; lines(22,7)=1; lines(22,8)=1; lines(22,9)=1; lines(22,21)=1; lines(23,6)=1; lines(23,24)=1; lines(23,26)=1; lines(24,23)=1; lines(24,6)=1; lines(24,5)=1; lines(24,4)=1; lines(24,25)=1; lines(24,26)=1; lines(25,24)=1; lines(25,4)=1; lines(25,3)=1; lines(25,1)=1; lines(26,25)=1; lines(26,24)=1; lines(26,23)=1; lines(26,27)=1; lines(27,26)=1; lines(27,21)=1; lines(25,26)=1; lines(23,22)=1; ``` 2. 再利用MATLAB中的shortestpath函数绘制基于Dijkstra算法的有向图 ```bash %绘制图节点和边 G = digraph(lines); [path1,d1] = shortestpath(G,1,15,'Method','positive'); [path2,d2] = shortestpath(G,15,12,'Method','positive'); [path4,d4] = shortestpath(G,12,15,'Method','positive'); [path3,d3] = shortestpath(G,15,27,'Method','positive'); path3 = [path4, path3]; path1 = [path1,path2(2:end)]; figure(2) p = plot(G,'Linewidth',3); hold on highlight(p,path1,'EdgeColor','m') highlight(p,path2,'EdgeColor','m') highlight(p,path3,'EdgeColor','m') lines(lines==0)=inf; %将lines=0的数全部替换为无强大 hold off ``` 绘制出的有向图如图所示：（此例程位于[MATLAB轻松绘制地图路线——已知及未知坐标下的处理方法(1)](https://waynegao.blog.csdn.net/article/details/112647925)的工程文件——“第一关”中）  若节点太多，可通过循环命令构建邻接矩阵。假设现有92个节点，节点间的距离也不再为等长，而是Demo2中计算出的距离： ```python %% 基于MATLAB_shortestpath_Dijkstra算法绘制有向图 n=92; %设置邻接矩阵大小 temp=1; %设置起点 lines = zeros(92,92); for i = 1:140 lines(dist_A(i,1),dist_A(i,4)) = dist_A(i,7); lines(dist_A(i,4),dist_A(i,1)) = dist_A(i,7); %注意不要漏掉对称赋值，否则只能构建出单向图，很多路线无法往返，不通 end %绘制图节点和边 G = digraph(lines); % lines(lines==0)=inf; %将lines=0的数全部替换为无穷大 count = 1; distance = zeros(260,1); for j = 1:20 for k = data4_A' eval("[path"+num2str(count)+",distance(count,:)]= short