【路径规划】基于dijkstra 算法实现图像地图最短路径求解附matlab代码

简介: 【路径规划】基于dijkstra 算法实现图像地图最短路径求解附matlab代码

1 简介

对任意图,选择合适的数据结构表示图,在此基础上实现求解最短路径的Dijkstra算法。对所设计的图的数据结构,提供必要的基本功能。建立图的表示模块,顶点的插入和删除操作模块;在建立图之后从单源点开始求最短路径并显示。实现的功能有建立有向图,排除和增加目的地,方便找出最短路径,在建立好的有向图中,显示出来从顶点到各个顶点的最短路径。

Dijkstra算法的基本思路是:假设每个点都有一对标号(dj, pj),其中dj是从起源点s到点j的最短路径的长度(从顶点到其本身的最短路径是零路(没有弧的路),其长度等于零);pj则是从s到j的最短路径中j点的前一点。求解从起源点s到点j的最短路径算法的基本过程如下:

1)初始化。起源点设置为:①ds=0, ps为空;②所有其他点: di=∞, pi=;③标记起源点s,记k=s,其他所有点设为未标记的。

2)检验从所有已标记的点k到其直接连接的未标记的点j的距离,并设置:dj=min[dj, dk+lkj]式中,lkj是从点k到j的直接连接距离。

3)选取下一个点。从所有未标记的结点中,选取dj中最小的一个i:di=min[dj,所有未标记的点j]点i就被选为最短路径中的一点,并设为已标记的。

4)找到点i的前一点。从已标记的点中找到直接连接到点i的点j*,作为前一点,设置:i=j* 5)标记点i。如果所有点已标记,则算法完全退出,否则,记k=i,转到2)再继续。

2概要设计

在任意图中实现求最短路径问题,首先是要能成功的在内存中输入图的信息,图的信息有两个,一是顶点个数,二是每两点之间的权值信息。当建立图之后,对图进行遍历才能使用Dijkstra算法求出最短路径,所以,建立图这一步很关键。在实际使用当中,顶点的信息是成千上万,而且是随时可能产生变动,故建图模块要实现顶点的删除和插入操作;在完成了图的建立之后,用Dijkstra算法的思想,从单源点开始,求出到各个顶点的最短路径,并能够实现显示功能,这也是程序实际化的要求。

3建图过程

能把一个带有顶点和权值的数据结构图输入电脑首先要用到数组,存储每个顶点信息以及每两个顶点构成的线路的权值。在建图的过程中,图的信息不是一成不变的,所以在实现初步输入图的信息后,要有删除和插入操作。需要插入顶点的时候,回归到初始建图模块,但是这个操作是在已建立的图上操作,而非在清除内存之后进行插入,所以,要实现插入的高效和实用性。在删除顶点的时候,在已建立的图上进行删除,首先对图进行遍历,只要是和欲删除的顶点有关联的边值都要删除掉,这样就实现了顶点的删除操作,目的是提高用户使用程序的效率,对已知或者误录入的顶点进行排除,增加了程序的人性化。

2 部分代码

function [p1,p2]=ConvertPos2Point(G,x,y)imgcol=size(G.map,2);imgrow=size(G.map,1);row=round(imgrow/G.drate); col=round(imgcol/G.drate); c=1;for i=1:size(x,1)    x1=uint32(y(i)/G.drate);    y1=uint32(x(i)/G.drate);    if ((x1>=row ) || ( y1>=col) || (x1<1 ) || ( y1<1))         fprintf('points are out of range!\n');        continue;    end    if (mod(i,2))        p1(c)=(y1+1)+(col*(x1));    else        p2(c)=(y1+1)+(col*(x1));        c=c+1;    endend

3 仿真结果

4 参考文献

[1]潘峥嵘, 陈晓宇, 郭凯,等. 基于电子地图和Dijkstra算法路径规划的实现[J]. 测绘科学, 2010, 35(4):3.

博主简介:擅长智能优化算法、神经网络预测、信号处理、元胞自动机、图像处理、路径规划、无人机等多种领域的Matlab仿真,相关matlab代码问题可私信交流。

部分理论引用网络文献,若有侵权联系博主删除。


相关文章
排队算法的matlab仿真,带GUI界面
该程序使用MATLAB 2022A版本实现排队算法的仿真,并带有GUI界面。程序支持单队列单服务台、单队列多服务台和多队列多服务台三种排队方式。核心函数`func_mms2`通过模拟到达时间和服务时间,计算阻塞率和利用率。排队论研究系统中顾客和服务台的交互行为,广泛应用于通信网络、生产调度和服务行业等领域,旨在优化系统性能,减少等待时间,提高资源利用率。
基于HMM隐马尔可夫模型的金融数据预测算法matlab仿真
本项目基于HMM模型实现金融数据预测,包括模型训练与预测两部分。在MATLAB2022A上运行,通过计算状态转移和观测概率预测未来值,并绘制了预测值、真实值及预测误差的对比图。HMM模型适用于金融市场的时间序列分析,能够有效捕捉隐藏状态及其转换规律,为金融预测提供有力工具。
基于GoogleNet深度学习网络的手语识别算法matlab仿真
本项目展示了基于GoogleNet的深度学习手语识别算法,使用Matlab2022a实现。通过卷积神经网络(CNN)识别手语手势,如&quot;How are you&quot;、&quot;I am fine&quot;、&quot;I love you&quot;等。核心在于Inception模块,通过多尺度处理和1x1卷积减少计算量,提高效率。项目附带完整代码及操作视频。
|
4月前
|
【2023高教社杯】D题 圈养湖羊的空间利用率 问题分析、数学模型及MATLAB代码
本文介绍了2023年高教社杯数学建模竞赛D题的圈养湖羊空间利用率问题,包括问题分析、数学模型建立和MATLAB代码实现,旨在优化养殖场的生产计划和空间利用效率。
224 6
【2023高教社杯】D题 圈养湖羊的空间利用率 问题分析、数学模型及MATLAB代码
【2022年华为杯数学建模】B题 方形件组批优化问题 方案及MATLAB代码实现
本文提供了2022年华为杯数学建模竞赛B题的详细方案和MATLAB代码实现,包括方形件组批优化问题和排样优化问题,以及相关数学模型的建立和求解方法。
141 3
【2022年华为杯数学建模】B题 方形件组批优化问题 方案及MATLAB代码实现
【2023五一杯数学建模】 B题 快递需求分析问题 建模方案及MATLAB实现代码
本文介绍了2023年五一杯数学建模竞赛B题的解题方法,详细阐述了如何通过数学建模和MATLAB编程来分析快递需求、预测运输数量、优化运输成本,并估计固定和非固定需求,提供了完整的建模方案和代码实现。
110 0
【2023五一杯数学建模】 B题 快递需求分析问题 建模方案及MATLAB实现代码
耐震时程曲线,matlab代码,自定义反应谱与地震波,优化源代码,地震波耐震时程曲线
地震波格式转换、时程转换、峰值调整、规范反应谱、计算反应谱、计算持时、生成人工波、时频域转换、数据滤波、基线校正、Arias截波、傅里叶变换、耐震时程曲线、脉冲波合成与提取、三联反应谱、地震动参数、延性反应谱、地震波缩尺、功率谱密度
基于混合整数规划的微网储能电池容量规划(matlab代码)
基于混合整数规划的微网储能电池容量规划(matlab代码)
含多微网租赁共享储能的配电网博弈优化调度(含matlab代码)
含多微网租赁共享储能的配电网博弈优化调度(含matlab代码)
基于Logistic函数的负荷需求响应(matlab代码)
基于Logistic函数的负荷需求响应(matlab代码)