一种改进的Dijkstra算法的分析及程序实现

20111JISUANJIYUXIANDAIHUA185:10062475(2011)01003603:20101008:(1975),,,,,:,Dijkstra(哈尔滨金融学院计算机系,黑龙江哈尔滨150030):Dijkstra算法是求有向图中从某一源点到其余各点最短路径的算法本文通过对传统的Dijkstra算法进行分析,提出一种改进算法,经理论分析,对于顶点数较多而边数较少的有向稀疏图来说,在求最短路径时能够大大提高算法的运行效率:最短路径;Dijsktra算法;改进算法:TP311:Ado:i10.3969/.jissn.10062475.2011.01.010ProgramImplementationandAnalysisonanImprovedDijkstraAlgorithmHAOChunmei(ComputerScienceDepartment,HarbinUniversityofFinance,Harbin150030,China)Abstract:Dijkstraalgorithmisanalgorithmforsolvingsinglesourceshortestpathsofdirectedgraph.ThispaperanalyzesclassicalDijkstraalgorithmandputsforwardanimprovedalgorithm.Bytheoreticalanalysis,theimprovedalgorithmcanimproveefficiencyofdirectedsparsegraph.Keywords:shortestpath;Dijkstraalgorithm;improvedalgorithm0,,,,DijkstraC,,1DijsktraDijkstra,,G=(V,E),V,E,:cost;S,v0;dist[n]pre[n],dist,dist[i]=cost[v0][i];prev,pre[i]=v0;VSw,dist[w],wS,w,S,idist[w]+cost[w][i]dist[i],,w,v0wi,dist[i],dist[i],dist[w]+cost[w][i]dist[i],pre[i]w,w,pre[i];n,n1,n1C:voiddijkstra(MGRAPH*g){intdist[MAXSIZE],s[MAXSIZE],v0,,i,jk,w;printf(:);scanf(%d,&v0);for(i=1;i=gvexnum;i++){dist[i]=garcs[v0][i];pre[i]=v0;s[i]=0;}s[v0]=1;for(i=2;i=gvexnum;i++)2011年第1期郝春梅:一种改进的Dijkstra算法的分析及程序实现37{min=INFINITY;for(j=1;j=gvexnum;j++)if((dist[j]min)&&(s[j]==0)){min=dist[j];w=;j}s[w]=1;for(k=1;k=gvexnum;k++)if((s[k]==0)&&(dist[w]+garcs[w][k]dist[k])){dist[k]=dist[w]+garcs[w][k];pre[k]=w;}}}12~25,n,O(n2),O(n2)Dijkstra:(1)VSw,wdist,S,w,;(2)w,,S,dist,Sdist;(3)w,dist,2DijkstraDijkstra,:,,,,S,v0;dist,,dist,,;prev,pre[i]=v0;heap,heap,,heapv0;m,v0,0;heap,w,S,,m,w,wSvi,dist,distheap,k;k,S,,S:1,Dijkstra,111Dijkstra01234w2435s{1}{1,2}{1,2,4}{1,2,4,3}{1,2,4,3,5}dist[2]1010101010[3]!60505050[4]3030303030[5]100100906060pre[2]11111[3]12444[4]11111[5]11433m[1]00000[2]10000[3]03100[4]21000[5]32210heap[1]102304503605[2]3041005905[3]1005603DijkstraC:voiddijkstra(ADJGRAPH*g){intdist[MAXSIZE],s[MAXSIZE],v0,,i,jk,w,m[MAXSIZE];HEAPheap[MAXSIZE],temp;ADJNODE*p;38计算机与现代化2011年第1期printf(:);scanf(%d,&v0);for(i=1;i=gvexnum;i++){dist[i]=INFINITY;pre[i]=v0;s[i]=0;m[i]=0;}i=1;p=gadjlist[v0].link;while(p!=NULL){dist[padjvex]=pdata;heap[i].vertex=padjvex;m[padjvex]=;iheap[i].data=dist[padjvex];p=pnext;i++;}k=i1;s[v0]=1;for(i=2;i=gvexnum;i++){heapadj(heap,k,m);w=heap[1].vertex;s[w]=1;m[w]=0;temp=heap[1];m[heap[k].vertex]=1;heap[1]=heap[k];heap[k]=temp;k;p=gadjlist[w].link;while(p!=NULL){if((s[padjvex]==0)&&(dist[w]+pdatadist[padjvex])){dist[padjvex]=dist[w]+pdata;pre[padjvex]=w;if(m[padjvex]==0){k++;heap[k].data=dist[padjvex];heap[k].vertex=padjvex;}elseif(heap[m[padjvex]].data!=dist[padjvex]){heap[m[padjvex]].data=dist[padjvex];heap[m[padjvex]].vertex=padjvex;}}p=pnext;}}}Dijkstra,,,E,,log2n,N,O(N(log2N+E)),DijkstraDijkstra3Dijkstra,,,,,DijkstraDijkstra:[1].Dijkstra[J].,2003,39(3):99101.[2].Dijkstra[J].,2006,25(3):3032.[3]ThomasHCormen,CharlesELeiserson,RonaldLRivest,eta.lIntroductiontoAlgorithm[M].:,2001.[4].[J].,2006(2):8485.[5],.DijkstraGIST[J].,2010,26(1):3940.[6].Dijkstra[J].,2009(5):6164.[7],.Dijkstra[J].,2008(3):3537.[8].[J].,2000,21(5):472474.[9].Dijkstra[J].,2009(5):8284.[10].[J].,1995(2):512.[11]CherkasskyBV,GoldbergAV,RadzikT.Shortestpathsalgorithm∀stheoryandexperimentalevaluation[J].MathematicalProgramming,1996,73(2):129174.[12],.(C)[M].:,2009.[13],,.GISDijkstra[J].,2007(8):289291.[14],.[J].,2005,31(13):9398.