最短路径算法中Dijkstra算法的优化及应用(3)
时间:2017-04-11 13:20 来源:毕业论文 作者:毕业论文 点击:次
void MGraph<T>::Dijkstra(int s,T*& d, int *& path) { int k,i,j; if(s<0||s>n-1)throw OutOfBounds; bool *inS=new bool[n];d=new T[n];path=new int[n]; for(i=0; i<n; i++){ //初始化 inS[i]=false; d[i]=a[s][i]; //a是有向图G的邻接矩阵 if(i! =s && d[i]<INFTY) path[i]=s; Else pash[i]= -1; } inS[i]=true; d[s]=0; //将源点加入S中 for(i=1; i<n-1; i++){ //求n-1条最短路径 k=Choose( d, inS); //选出下一条最短路径的的结点k inS[k]=true； //将k加入S中 for (j=0; j<n; j++) //更新d和path的值 if (! inS[i]&& d[k]+a[k][j]<d[j]){ d[j]=d[k]+a[k][j]; path[j]=k; } } } 3.优化的Dijkstra算法 3.1 两种Dijkstra优化算法 第一类优化算法——减小算法中成功搜索范围 减小算法中成功搜索的搜索范围以尽快到达目标节点。在对现实问题中的交通图初始化为网络拓扑图时，虽然终点已知，而源点尚未确定，但依据常识离案发地段最近的派出所应为案发地段所在辖区派出所，或其周边派出所，也就是源点的选取范围可以确定利用MapObjects2组件提供的MapLayer.SearchExpression (expression)记录集筛选方法，根据案发地段(终点)的不同，动态选取案发地段所在辖区及相邻辖区的道路图层及派出所图层数据进行最短路径查询，从而有效地减少了拓扑图中节点总数 的值。 第二类优化算法——改进算法的存储结构 在实际工作中，还要建立起空间数据结构。网络数据结构使用的是“边和节点”的数据结构，该数据结构是建立在图论的基础上，节点可用来定义边的连接关系。对于网络数据的存储，传统的是采用图论中的邻接矩阵方法，其存储量为 ( 为网络中节点数)。通常的地理网络，尽管节点很多，但与节点相关联的节点数目并不多，一般都为稀疏图，将会浪费大量的空间。若采用邻接表的链式存储结构，其存储量为 ( 为节点列表中，同节点关联的所有边的数目)，可节省大量的存储空间，尤其是在表示与节点和边相关信息较多的地理网络时，更为有效。但邻接表却难以判断两节点之间的关系，因此本文提出利用。.NET框架提供的特殊类Hashtable。.NET框架包含特殊类，比如通常所说的集合类用于存储对象。与数组类似，集合类可以把对象放入容器中，然后再取出。但集合的使用方法与数组不同，拥有用于插入和删除项的专用方法。使用Hashtable最大的优点就是大大降低数据存储和查找的时间花费，几乎可看成是常数时间。 3.2 优化的Dijkstra算法 本文采用第一类优化算法减小搜索范围的思路来对Dijkstra算法进行优化。Dijkstra算法用来求解图上从任一节点(源点)到其余各节点的最短路径。采用邻接矩阵存储网络拓扑结构，需要 的存储空间，随着节点数 的增大，其计算效率和存储效率越低。本文在对传统Dijkstra算法分析的基础上，对其进行了优化，优化算法只对最短路径上节点的邻居做处理，而不涉及到其他节点。 (责任编辑：qin) |