基于图的路径规划算法对比

算法说明与实现效果

通过构造邻接矩阵，在构造的路网中找到一个节点通向另一个节点的最短路径，包括DJ，Floyd，A*，ACO，GA算法。
路网与一般的无向图不同点是：在一般的无向图中，从起点开始，不论下一次选择哪个节点，最终都可以到达目标节点；而路网中存在死路，即算法需要回溯才能找到正确的通路

一般的无向图：

100个节点的路网中的路径规划：

1000个节点的路网中的路径规划：

根据路网生成的带权无向图：

构造路网

1.打开Arcmap

电脑上打开软件：ArcMap

2.新建Shapefile文件

右键ArcCatalog中文件夹链接下的目录，依次选择“新建”->“Shapefile”

3.编辑Shapefile属性

在弹出的创建新Shapefile对话框中，填写文件名称，选择要素类型为“折线”，点击“编辑”，弹出空间参考属性对话框，选择XY坐标系:地理坐标系->world->WGS 1984，最后点击“确定”，坐标将包含M值”和“坐标将包含Z值”千万不要勾选，否则后面路网数据处理过程中会报错，最后点击“确定”

4.开始编辑

左侧图层中出现了我们刚新增的Shapefile线类型图层，我们依次点击“编辑器”->“开始编辑”

5.创建要素并绘制路网

点击‘创建要素’，在右边侧栏中选中创建的文件，之后开始编辑

6.打断相交线

绘制编辑完道路数据后，依次点击工具栏中的“编辑器”->“更多编辑工具”->“高级编辑”，选中全部要素，然后点击高级编辑工具栏中的“打断相交线”

7.保存编辑

打断完成之后，依次点击“保存编辑内容”->“停止编辑”
注：若打断失败可以重启arcmap，重新新建文件，以上步骤重新来一次！！！

8.打开图层属性表

右击‘road’，打开属性表

9.添加字段

添加点与路径长度的字段
注：一定要保证‘停止编辑’了，才可以更改字段

10.完成字段添加

添加完成后的字段如下表所示

11.计算字段id

计算字段id的内容：右键Id字段，选择“字段计算器”，在字段计算器中，给Id进行重新计算赋值，双击FID字段，然后点击+，再输入数字1即可

12.计算点线字段

计算x1,y1,x2,y2字段：选中列x1并右击，选择‘计算几何’，选择‘线起点的x坐标’，点击确定，其余的y1，x2，y2同理

13.选中length字段

计算length字段，即计算路径长度：选中length列->选择字段计算器

14.计算length字段

在字段计算器中，选择解析程序为python，输入以下内容计算路径长度，点击确定

math.sqrt(( !x1! - !x2! )*( !x1! - !x2! )+( !y1! - !y2! )*( !y1! - !y2! ) )

15.导出路网数据

导出路网数据到表格

16.查看最终的路网数据

在表格中查看最终的路网数据

路网数据转化为图

将保存的excel数据加载到matlab中，编写并运行以下的matlab代码，得到路网与图
路网：

无向带权图：

matlab代码

（1）将原始的road数据（即保存的excel数据）转化为图和邻接矩阵的matlab代码

%% 函数功能：
%(1)读取arcmap数据，进行点合并，绘制路网图，保存处理后的数据
%(2)坐标编号，坐标关系转化为点关系，根据点关系得到邻接矩阵
%(3)根据邻接矩阵构造图
%data属性:fid id x1 y1 x2 y2 length%% 返回值：
%A：邻接矩阵
%G：无向图
%data：原始数据的所有坐标
%uniqueValues:不重复的节点坐标及其对应的唯一id
%% 读取数据
%文件名
filename = 'road.xls';
% 指定要读取的文件名和工作表名
sheet = 1;  % 第一个工作表
% 使用xlsread函数读取数据  header为列名称
[data, header] = xlsread(filename, sheet);
data=data(:,2:7);%读取列
%data属性:id x1 y1 x2 y2 length
name_id = data(:,1);%记录id
start_point=data(:,2:3);%记录起点坐标x1 y1
end_point=data(:,4:5);%记录终点坐标x2 y2
length_list=data(:,6);%记录路径长度length%% 处理数据：合并距离很近的点
distanceThreshold=3;%距离阈值，两点距离小于此阈值则合并两个点
numNodes = size(start_point, 1);
for  kk = 1:5%通过迭代，不断减少距离阈值distanceThreshold=distanceThreshold/2;Preprocessed_data=[];%记录要替换的数据for i = 1:numNodesfor j = 1:numNodesif i ~= jdistance1 = norm(start_point(i, :) - start_point(j, :));if distance1 <= distanceThreshold%两点距离过近Preprocessed_data=[Preprocessed_data;start_point(i, :),start_point(j, :)];enddistance2 = norm(end_point(i, :) - end_point(j, :));if distance2 <= distanceThreshold%两点距离过近Preprocessed_data=[Preprocessed_data;end_point(i, :),end_point(j, :)];enddistance3 = norm(start_point(i, :) - end_point(j, :));if distance3 <= distanceThreshold%两点距离过近Preprocessed_data=[Preprocessed_data;start_point(i, :),end_point(j, :)];endendendend%for%根据记录处理原始数据for i = 1:size(data,1)for j = 1:size(Preprocessed_data,1)if data(i,2)==Preprocessed_data(j,1) && data(i,3)==Preprocessed_data(j,2)data(i,2)=Preprocessed_data(j,3);data(i,3)=Preprocessed_data(j,4);end    if data(i,4)==Preprocessed_data(j,1) && data(i,5)==Preprocessed_data(j,2)data(i,4)=Preprocessed_data(j,3);data(i,5)=Preprocessed_data(j,4);end    end    end%for    %重新读取数据name_id = data(:,1);%记录idstart_point=data(:,2:3);%记录起点坐标end_point=data(:,4:5);%记录终点坐标length_list=data(:,6);%记录路径长度
end
% %重新计算路径长度
% data(:,6) = norm(data(:,2:3) - data(:, 4:5));
%% 绘制路网
figure(1);
hold on;
% 逐个连接起点和终点
for i = 1:size(start_point, 1)x = [start_point(i, 1), end_point(i, 1)];y = [start_point(i, 2), end_point(i, 2)];distance=sqrt((start_point(i, 1)-start_point(i, 2))^2+(end_point(i, 1)-end_point(i, 2))^2);if distance>0.1%两点距离过近则删除%  text(start_point(i, 1),start_point(i, 2),num2str(i),'color','r','FontSize', 12);%图上打上名称plot(x, y, 'b-o'); % 使用蓝色圆形标记连线end
end
% 设置坐标轴范围和标签
xlabel('X轴');
ylabel('Y轴');
% 添加标题和图例
title('路网');
legend('节点');
hold off;%% 保存数据到表格
% 创建表格
T = array2table(data, 'VariableNames', {'Id', 'x1', 'y1','x2','y2','length'});
% 保存表格数据到 CSV 文件
filename = 'data.csv';
writetable(T, filename);%% 二维数组去重值,计算剩余的节点数
uniqueValues = unique(data(:,2:3), 'rows');
node_length = size(uniqueValues,1);
fprintf('路网中包含节点的数目为：%d \n\n',node_length)%% 给数据的坐标编号，使每个坐标具有唯一id
for i = 1:node_lengthuniqueValues(i,3)=i;
end    %% 将data数据中的点的关系转化为id的关系
new_data = zeros(size(data,1),3);
for i = 1:size(data,1)for j = 1:size(uniqueValues,1)if data(i,2)==uniqueValues(j,1) && data(i,3)==uniqueValues(j,2)new_data(i,1)=uniqueValues(j,3);endif data(i,4)==uniqueValues(j,1) && data(i,5)==uniqueValues(j,2)new_data(i,2)=uniqueValues(j,3);endend
end
new_data(:,3)=data(:,6);%载入路径权值，即路径长度
save('data.mat', 'new_data');%% 根据id的关系绘制邻接矩阵
edges=new_data(:,1:2);%载入边的关系
% 提取节点数量
numNodes = max(edges(:));
% 创建空的邻接矩阵
adjMatrix = zeros(numNodes);
% 根据边关系设置邻接矩阵
numEdges = size(edges, 1);
for i = 1:numEdgesstartNode = edges(i, 1);endNode = edges(i, 2);if startNode==0 ||endNode==0continue end     adjMatrix(startNode, endNode) = new_data(i, 3);%记录权值
end
A = adjMatrix+adjMatrix';%转置得到对称阵
G = graph(A, 'upper', 'omitselfloops');%创建无向图 
figure(2);%开启画图
h = plot(G, 'EdgeLabel', G.Edges.Weight,'EdgeLabelColor','r');
layout(h, 'force');   % 使用强制布局算法进行节点布局

（2）根据邻接矩阵进行二维路径规划的完整matlab代码
完整代码过一段时间在github上开源。

实现效果：