Dijkstra算法的优化

第30卷第22期计算机工程2004年11月VoL30N22Computer EngineeringNovember 2004●人工智能及识别技术●文章编号: 1000 -24000-01- -02文献标识码: A中圈分类号: TP311Dijkstra算法的优化余冬梅，张秋余，少林,方邕(兰州理工大学电信学院，兰州730050)摘要:在求解最优路径时经常使用经典的Dijkstrm算法，但在实际应用当中计算最优路径时非常消耗内存空间和计算时间。在物资筹供决策系统的开发过程中，结合实际应用情况，对Dijkstra算法进行 了优化，大大降低了内存消耗和计算时间。最后利用C++语言对算法进行了详细的算法描述。关键词: Dijksra; 最短路径; C++Optimized Dijkstra AlgorithmYU Dongmei, ZHANG Qiuyu, MA Shaolin, FANG Ting(College of Telecommunication, Lanzhou University of Technology, Lanzhou 730050)[Abstract] In shot path calcuating, Dijkstra algorithm is used, but it needs more memory and computer time. In the developmcnt of material providedecision making systen , the pape optimizes the Djkstra algorihm, it saves much memory and calculating time, and describcs it with C++ language.[Kcy words] Dijkstra; Shortest path; C++Djjkstra算法是图论中求最短路径的一个著名的算法，论简单图(无环和重边)。使用改进算法求从顶点V0(称为源使用其可以求得图中-一点到其他 各顶点的最短路径树，但在点)到其它各顶点的最短路径长度和所经过的最短路径，存实际应用当中，使用Dijkstra算法耗费大量的内存空间和计储结构如下。算时间，虽然有很多人对Dijkstra算法提出了一些改进的算(1)用链表数组MGraph来存储矩阵G。将邻接矩阵的每法，但都没有达到最理想的结果。作者在《物资筹供决策系一行用一个单链表来表示，链表中只有非∞的元素，每个节统》开发过程中，根据实际情况对D算法在存储空间和计算点有两个元素，一个为所在的列值，一个为此点的权值，图时间上均做了优化，使Djkstra算法 在求解最短路径时达到1中无向图的存储格式如图2所示。时间下限。1 Dijkstra算法描述Djkstra提出了一个按路径长度递增的次序产生最短路4|径的算法，首先引进一个辅助向量D，它的每个分量D[]为弧上的权值，否则置D[i为∞。显然，长度为D[] = Min{D3[i]|vi∈V}的路径就是从v出发的长度最短的一-条最短路径。此路径为(，vi)。圜I无向圈假设下一条长度次短的最短路径的终点是vk，则可想G1而知，这条路径或者是(v, vk),或者是(v, v, vk)。它的长度2+2T ]T囚或者是从v到vk的弧上的权值，或者是Dj]和从vj到vk的弧上的权值之和。[G--般情况下，假设S为已经求得最短路径的终点集合，4+241 JF@工3F>331则可证明:下一条最短路径(设其终点为x)或者是弧(v, x)，65+2T子口或者是中间只经过S中的顶点而最后到达顶点x的路径。这可用反证法来证明。假设此路径上有一个顶点不在S中，则圈2存储格式说明存在一- 条终点不在S而长度比此路径短的路径。但是这其C++代码如下描述:是不可能的，因为我们是按路径长度递增的次序来产生各最typeder struct {短路径的，故此长度比此路径短的所有路径均已产生,它们MNode * next;的终点必定在S中，即假设不成立。因此在-一般情况下，下}MNode;一条长度次短的最短路径的长度必是class MCraph/邻接矩阵Di] = Min{D[i] |vi∈V_S }public:其中，D[i]或者是弧(V, vi)上的权值，或者是D[](vk∈S)和上的权值之和。中国煤化工= curent;}2优化后的存储结构MHCNMHG设一个带权有向图为G, G=(V, T),其中V为顶点集作者简介:余冬梅(1953-),女副教授，主研方向:软件总线;合，T为边的集合。G中顶点数为,该算法中的图C限于讨张秋余，教授;马少林、方霆， 硕士生收稿日期: 2003-09-26E-mail: msl _uck@hotmail.com-145--void SetFirst(MNode *p){ first = p:current = first;}{MNode* GotfFirt(ifirst){urrent = frstreturm current;}D[pnode~>r] = pnode~>v;else return NULL;}ChainNode *|= new Node);void Add(MNode *p){current->next=p; current=p;}.>r - pnode>r,MNode *Necx()ifcurrnen->nex(){urreat = current->next;p[pnode->r] = v0;return curent;}else retum NULL:}L.AddTaiK);pnode = pnode->next; }(2)一维数组D来存储各顶点到V0的最短距离。while(L.IsEmpty()(3)用一维数组P来存储前驱点。min = INFINITY;(4)用-一个辅助双向链表，用来存储正在参与比较的节cn2 = L.First();点,使用双向链表的目的是在删除节点时降低时间复杂度。while(en2)}{其C++代码如下描述:i(D[cn2>r]r;Node◆next,◆prev;min = D[w];}}ChainNode;cn2 = L.Next();class Path {L. Delete(cn/)//删除已经找到最短的节点public:pnode = G[w]frst;ChainNode first,current;while(pnode)int n;{i{D[pnode->)] > (min+ pnode->V))Path(){n=0; current = NULL; first = NULL;}{iD[pnode~>r] == INFINITY)void StFirst(ChainNode* p){frst = p; current = first; n=;}{ChainNode * pNode = new ChainNode);ChainNode* Fist({fitcturrent-firstelse current=pNode->r“pnode->r;NUL:; retum curent}LAdTail(pNode);void AddTai(ChainNode *p){current->next=p:p->prev=D[pnode~>r] = min+pnode->v;current;curent=p; n++;}int Delete(ChainNode *p);p[pnode->r} =w;ChainNode *Next){if(curnext){curent = current->pnode- pnode->next; } }next;returm current;}elsc return NULL}return true; }bool IsEmpty(){retum n==0;}4复杂度分析3优化后的算法(1)空间复杂度分析:由于采用了链表数组，因此空间实际应用中的邻接矩阵大多是稀疏矩阵,在计算过程中复杂度为0(T), T为有向图的边数，对于最差情况下如果有大量的∞参与计算，所以改进算法的主要思路就是消除冗T=n?,那么空间复杂度为0(m7)。氽存储和冗余计算。(2)时间复杂度分析:用一个链表数组MGraph G[]来表示邻接矩阵，算法I)步骤l)的复杂度为0(n)。2)步骤2)的复杂度为0(n)。步骤如下:(1)将与v0直接相连的节点的D[vi]初始化为其权值,其3)步骤3),第一次循环的次数为与v0直接相连的顶点的个数nI,第二次循环次数为n1-I再加上与第一次找到的顶点直接相连且余的置为机器所允许的最大值。与v0的距离为无穷大的节点的个数。以此类推直到L中的节点个数(2)将与v0直接相连的顶点加入到链表Path中。为零为止。最坏情况下如果v0与其余个顶点都有直接相连，那么每(3)在Path中找到权值最小的节点w,并在Path中删除此次循环的次数为-1).(-2...1,那么时间复杂度为-1-+-+2+..+顶点，如果剩余节点数为0则结束。即为0(n)。(4)修改最短路径:在G里与w直接相连的其余各节点vi4)步骤4)的时间复杂度为0(T),对于任何最短路径算法必须至的权值中比较D[vi]与D[w]+s(w,vi)的大小，如果D[vi]小于少对每条边检查一次，因为任何一条边都有可能在最短路径中，因D[w]+s(w,vi) ,并且如果D[vi]为∞则将vi加入到Path中，然此步骤4)的时间复杂度为O(T)，当T=n?时， 复杂度为0(n2)，与Dijkstn算法相同。后将P[vi]的前驱设置为w，并修改最短路径D[vi]= D[w]+因此优化后的算法最坏时间复杂度为max{O(n),O(T),s(w,vi)。 重复步骤(2)。0(m)},即为0(m)。改进后的算法C++源代码如下:5结论bool ShortestPath OptDU(MGraph *G,int n, int v0, /PrevPoint*/优化后的算法经过在物资筹供决策系统的实际应用，算int *p/*ShortPathTable*/ int *D){ int w,imin;法的时间复杂度与Dijkstra算法- -样， 但在T<n ) retum fsl:/trow OutOfBounds();多堵文献for(i=0;i