最短路径分析的dijwsor算法

最短路径分析的dijwsor算法

最短路径分析是gis最基本的网络分析功能。在求解最短路径问题的算法中,Dijkstra算法是目前国内外一致公认的较好算法。现在许多计算机实现的算法都是在Dijkstra算法的基础上,运用关联矩阵、邻接矩阵的概念,使得存储网络数据和运算,都需要定义N×N(N为网络结点数)的矩阵。当网络的结点数较大时,将占用大量的存储空间,并且运算也很浪费时间。徐立华(1989)提出最大相关边数的概念,通过定义点-边相关矩阵,节省了存储空间,提高了运算速度,为计算机解决大网络问题提供了切实可行的算法。作者在Dijkstra算法基础上,对相关边算法进行改进,提出邻接结点算法,进一步提高运算速度。1相邻接收算法的基本概念1.1基于m条的最短路求解设已知图中对总长度来说最接近于结点S的m个结点,以及从结点S到这些结点中的每个结点的最短路。对结点S和这m个结点着色,然后最接近于S的第m+1个结点可这样求——对于每个未着色的结点,考虑所有已着色结点x,将弧(x,y)接在从S到x的最短路后面,从构成的S到y的m条不同路中选出最短路,就是S到y的最短路。从m=0开始,将此过程重复进行,直至求得S到T的最短路为止。传统的算法中应用关联矩阵和邻接矩阵存储网络数据,会有大量的无效的0元素或∞元素,占用大量存储空间。在此基础上进行矩阵运算,必将浪费大量运行时间。1.2用点-边相关矩阵计算相关边算法的关键是提出了最大相关边数的概念,即一个网络中各结点的相关边数的最大值称为网络的最大相关边数。取网络的最大相关边数作为矩阵的列,网络的结点数作为矩阵的行,构造相关矩阵R,表示网络结构。相关矩阵的行按结点号从小到大顺序排列,与结点i相关的边的边号写在矩阵的第i行。对照相关矩阵,把相关矩阵中各元素对应的边号的权值填在同一位置上,构造相应的初始判断矩阵dR。有了相关矩阵R和初始判断矩阵dR,根据Dijkstra算法的着色思想,就可以求网络中任意两点间的最短路径了。关键步骤是,在dR已标记的行中,求所有元素的最小值,并记下最小值的行和列。然后在R中取相同行列的元素,记为w,再在R的其它行中,寻找值为w的元素所在的行,将dR的对应行作标记。相关边算法用点-边相关矩阵描述网络结构,大大减少无效的0元素和∞元素,从而节约存储空间,提高运算速度。但是当网络结点数很多时,在R的其它行中寻找长值为w的元素的工作量也是很大的。为了进一步提高运行速度,可以对相关边算法进行改进。1.3网收稿编码的邻接结论矩阵在最大相关边数的启发下,作者提出最大邻接结点数的概念。一个网络中,各结点的邻接结点的最大值称为该网络的最大邻接结点数。取网络的最大邻接结点数作为矩阵的列,网络的结点总数作为矩阵的行,构造邻接结点矩阵J来描述网收稿日期∶1997−10−21¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯络结构。邻接结点矩阵的行按结点号从小到大顺序排列,与结点i邻接的结点号写在矩阵的第i行,如果结点i的邻接结点数小于最大邻接结点数,则以0填充,直到填满矩阵。对照邻接结点矩阵,把邻接结点矩阵中各元素邻接关系对应的边的权值填在同一位置上(∞对应0元素),构造相应的初始判断矩阵dJ。邻接结点矩阵J和相关矩阵R虽然占用存储空间相等,但是邻接结点矩阵为在计算机实现过程中进一步提高运算速度,提供了更加有效的网络结构组织方式。2实现接口算法的方法2.1种最短路径为了使读者了解邻接结点算法求解最短路径问题的具体过程,现举一例说明(图1)。1)从数据文件中装载网络数据,网络的结点和边分别获得计算机的内部序号。需要说明的是,网络结点和边的内部序号和实际编号,有可能不相同。为了增加算法的灵活性,算法使用内部编号参与运算。(这里假设内部序号和实际编号相同)。2)求网络的最大邻接结点数m-iNodeNumMax。该网络各结点的邻接结点数的最大值m-iNodeNumMax=5。3)构造邻接结点矩阵m-pJ,各行中的结点序号可以前后随意放置。对应邻接结点矩阵各元素,构造初始判断矩阵m-pDj。⎛⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜2122153310854506367790360379105000709080000080000000⎞⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎛⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜1111108125151761412819∞51097166∞1010∞199161430∞∞∞15∞30∞7∞∞∞∞∞17∞∞∞∞∞∞∞⎞⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟图2邻接结点矩阵和初始判断矩阵4)有邻接结点矩阵和初始判断矩阵,就可以求网络中任意两点间的最短路径。若起点S,终点为T。第一步,初始化标记向量P,Pi=-1,i=1,2,…,m-iNodesNum,(m-iNodesNum为网络结点总数):第二步,根据起点S,标记初始判断矩阵m-pDj的第S行,Ps=0,记最短距离m-fDistanceMin=0;第三步,根据终点T,判断m-pDj的第T行是否已标记,是则转第五步,否则继续。第四步,在m-pDj已标记的行中,求所有元素的最小值dmin。若dmin=∞,说明不存在最短路径,则退出。否则m-fDistanceMin=dmin,记录最小值元素的行di、列dj。然后在邻接结点矩阵m-pJ中取(di,dj)元素,记为w。若第w行还未标记,则将m-pDj的第w行标记,Pw=di;并在m-pJ的第w行寻找值为di的元素,记录该元素的行ri、列rj。将m-pDj刚获得标记的行中各元素值均加上m-fDistanceMin,并使m-pDj的(di,dj)和(ri,rj)元素为∞。转第三步。第五步,从终点T开始,由标记向量P的分量循前点,直到起点S,查得最短路径m-pWays。m-fDistanceMin即为最短路径距离。假设求结点1到结点7的最短路径,过程如下。①初始化标记向量P;②P=0,m-fDistanceMin=0;③在m-pDj已标记的第1行中,dmin=11,di=1,dj=1,m-fDistanceMin=11;w=m-pJ=2,P=1,ri=2,rj=1;将m-pDj刚获得标记的第2行中各元素值均加上11,m-pDj=∞,m-pDj=∞;P=-1;④在m-pDj已标记的第1行和第2行中,dmin=12,di=1,dj=2,m-fDistanceMin=12;w=m-pJ=5,P=1,ri=5,rj=1;将m-pDj刚获得标记的第5行中各元素值均加上12,m-pDj=∞,m-pDj=∞;P=-1;⑤在m-pDj已标记的第1行、第2行和第5行中,dmin=17,di=5,dj=2,m-fDistanceMin=17;w=m-pJ=6,P=5,ri=6,rj=1;将m-pDj刚获得标记的第6行中各元素值均加上17,m-pDj=∞,m-pDj=∞;P=-1;⑥在m-pDj已标记的第1行、第2行、第5行和第6行中,dmin=19,di=2,dj=2,m-fDistanceMin=19;w=m-pJ=4,P=2,ri=4,rj=1;将m-pDj获得标记的第4行中各元素值均加上19,m-pDj=∞,m-pDj=∞;P=-1;⑦在m-pDj已标记的第1行、第2行、第4行、第5行和第6行中,dmin=21,di=2,dj=3,m-fDistanceMin=21;w=m-pJ=3,P=2,ri=3,rj=1;将m-pDj刚获得标记的第3行中各元素值均加上21,m-pDj=∞,m-pDj=∞;P=-1;⑧在m-pDj已标记的第1行、第2行、第3行、第4行、第5行和第6行中,dmin=26,di=6,dj=3,m-fDistanceMin=26;w=m-pJ=7,P=6,ri=7,rj=2;将m-pDj刚获得标记的第7行中各元素值加上26,m-pDj=∞,m-pDj=∞;⑨P=6→P=5→P=1,m-pWays=(1,5,6,7),m-fDistanceMin=26。2.2最短路径经过边串装采用面向对象的方法,可以把网络的最短路径算法生成库文件,以软件模块的形式提供给用户。抽象的路径类描述如下。classCRoute{//成员变量protected:CHAIN*m-pChains;//网络边集指针intm-iChainsNum;//边总数int*m-pPoints;//网络结点集指针intm-iNodesNum;//结点总数intm-iNodeNumMax;//最大邻接结点数float**m-pDj;//判断矩阵指针int**m-pJ;//邻接结点矩阵指针int*m-pWays;//最短路径经过边串指针intm-iWayNum;//最短路径经过边数floatm-fDistanceMin;//最短路径距离BOOLm-bIsLoaded;//是否数据装载成功//成员函数public:CRoute();//构造函数～CRouts();//析构函数public:BOOLLoadData(CStringstrPointFile,CStringstrLineFile);//数据装载BOOLbest(intiSP,intiEP);//求起点到终点的最短路径int*GetWay(int&iWayNum);//获得最短路径边串voidGetDistance(float&fDistance){fDistance=m-fDistanceMin;}//获得最短路径距离protected:voidpntkrm();//求最大邻接结点数voidarray();//构造邻接结点矩阵和初始判断矩阵voidchain();//最短路径经过点串的链化};其中CHAIN是网络拓扑结构体,描述如下。typedefstruct{ints-iNo;//边号ints-iSP;//始结点ints-iEP;//终结点floats-fLength//权值}CHAIN;作者已编写邻接结点算法VC++程序,并用于某测绘勤务保障系统的最短路径分析,取得了很好的效果。3节省运行速度一般说来,网络的结点数和边数是影响计算机内存和运行速度的主要原因。在实际应用中,复杂的网络实体,可以根据具体情况尽量减少网