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代码问题可私信交流。
部分理论引用网络文献,若有侵权联系博主删除。