Dijkstra算法.doc

Dijkstra算法Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN,CLOSE表方式，Drew为了和下面要介绍的A*算法和D*算法表述一致，这里均采用OPEN,CLOSE表的方式。其采用的是贪心法的算法策略大概过程：创建两个表，OPEN,CLOSE。OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。1访问路网中距离起始点最近且没有被检查过的点，把这个点放入OPEN组中等待检查。2从OPEN表中找出距起始点最近的点，找出这个点的所有子节点，把这个点放到CLOSE表中。3遍历考察这个点的子节点。求出这些子节点距起始点的距离值，放子节点到OPEN表中。4重复第2和第3步,直到OPEN表为空，或找到目标点。编辑本段算法实现#include#defineMaxNum765432100usingnamespacestd；ifstreamfin(Dijkstra.in)；ofstreamfout(Dijkstra.out)；intMap501501；boolis_arrived501；intDist501,From501,Stack501；intp,q,k,Path,Source,Vertex,Temp,SetCard；intFindMin()intp,Temp=0,Minm=MaxNum；for(p=1；p=Vertex；p+)if(DistpSourceVertex；for(p=1；p=Vertex；p+)for(q=1；qMappq；if(Mappq=0)Mappq=MaxNum；for(p=1；p=Vertex；p+)Distp=MapSourcep；if(Distp!=MaxNum)Fromp=Source；elseFromp=p；is_arrivedSource=true；SetCard=1；doTemp=FindMin()；if(Temp!=0)SetCard=SetCard+1；is_arrivedTemp=true；for(p=1；pDistTemp+MapTempp)&(!is_arrivedp)Distp=DistTemp+MapTempp；Fromp=Temp；elsebreak；while(SetCard!=Vertex)；for(p=1；p=Vertex；p+)if(p!=Source)fout=n；foutSource:SourcenTarget:pn；if(Distp=MaxNum)foutDistance:Infinityn；foutPath:NoWay!；elsefoutDistance:Distpn；k=1；Path=p；while(FromPath!=Path)Stackk=Path；Path=FromPath；k=k+1；foutPath:=1；q-)foutStackq；fout1=Source:2Target:3Distance:25Path:2-3=Source:2Target:4Distance:50Path:2-1-4=Source:2Target:5Distance:50Path:2-3-5=Source:2Target:6Distance:60Path:2-3-5-6=Source:2Target:7Distance:InfinityPath:NoWay!=示例程序及相关子程序：voidDijkstra(intn,intDistance,intiPath)intMinDis,u；inti,j；/从邻接矩阵复制第n个顶点可以走出的路线，就是复制第n行到Distancefor(i=0；iVerNum；i+)Distance=Arcn,i；Visited=0；/第n个顶点被访问，因为第n个顶点是开始点Visitedn=1；/找到该顶点能到其他顶点的路线、并且不是开始的顶点n、以前也没走过。/相当于寻找u点，这个点不是开始点nfor(i=0；iVerNum；i+)u=0；MinDis=No；for(j=0；jVerNum；j+)if(Visitedj=0&(DistancejMinDis)MinDis=Distancej；u=j；/如范例P1871图G6，Distance=No,No,10,No,30,100，第一次找就是V2，所以u=2/找完了，MinDis等于不连接，则返回。这种情况类似V5。if(MinDis=No)return；/确立第u个顶点将被使用，相当于Arcv,u+Arcu,w中的第u顶点。Visitedu=1；/寻找第u个顶点到其他所有顶点的最小路，实际就是找Arcu,j、j取值在0，VerNum。/如果有Arci,u+Arcu,jArci,j，则Arci,j=Arci,u+Arcu,jArci,j/实际中，因为Distance是要的结果，对于起始点确定的情况下，就是：/如果(Distanceu+Arcu,j)=Distancej则：/Distancej=Distanceu+Arcu,j；/而iPath保存了u点的编号；/同理：对新找出的路线，要设置Visitedj=0，以后再找其他路，这个路可能别利用到。例如V3for(j=0；jVerNum；j+)if(Visitedj=0&Arcu,jNo&u!=j)if(Distanceu+Arcu,j)=Distancej)Distancej=Distanceu+Arcu,j；Visitedj=0；iPathj=u；/辅助函数voidPrim()inti,m,n=0；for(i=0；i0)if(m=MinAdjNode(n)!=-1)Tn.Nodes.Add(Tm)；n=m；Visitedn+；elsen=MinNode(0)；if(n0)TMin2.Nodes.Add(TMin1)；Visitedn+；listBox1.Items.Add(Vn)；treeView1.Nodes.Add(T0)；voidTopoSort()inti,n；listBox1.Items.Clear()；StackS=newStack()；for(i=0；i=0；i-)if(InDegree(i)=0)S.Push(i)；Visited+；while(S.Count!=0)n=(int)S.Pop()；listBox1.Items.Add(Vn)；ClearLink(n)；for(i=VerNum-1；i=0；i-)if(Visited=0&InDegree(i)=0)S.Push(i)；Visited+；voidAOETrave(intn,TreeNodeTR,intw)inti,w0；if(OutDegree(n)=0)return；for(i=0；iVerNum；i+)if(w0=Arcn,i)!=0)listBox1.Items.Add(V+t+(w+w0).ToString()+t+i.ToString()+t+n.ToString()；TreeNodeT1=newTreeNode()；T1.Text=V+W=+(w+w0).ToString()+；TR.Nodes.Add(T1)；AOETrave(i,T1,w+w0)；voidAOE()inti,w=0,m=1；TreeNodeT1=newTreeNode()；for(i=0；iVerNum；i+)Visited=0；T1.Text=V0；listBox1.Items.Add(双亲表示法显示这个生成树：)；listBox1.Items.Add(VtWtIDtPID)；for(i=0；iVerNum；i+)if(w=Arc0,i)!=0)listBox1.Items.Add(V+t+w.ToString()+t+i.ToString()+t0)；TreeNodeT2=newTreeNode()；T2.Text=V+W=+w.ToString()+；AOETrave(i,T2,w)；T1.Nodes.Add(T2)；listBox1.Items.Add(tt树+m.ToString()；m+；treeView1.Nodes.Clear()；treeView1.Nodes.Add(T1)；intIsZero()inti；for(i=0；i=0)returni；return-1；in