《最短路的Dijkstra算法的程序源代码》由会员分享，可在线阅读，更多相关《最短路的Dijkstra算法的程序源代码（12页珍藏版）》请在金锄头文库上搜索。
1、关于最短路的Dijkstra算法的程序源代码! 悬赏分：150 | 解决时间：2009-1-25 00:57 | 提问者：hraper 最好是matlab的！急用！哪位高手有相关的程序请发到,谢谢！最佳答案 Dijkstra算法 Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。 Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。 Dijkstra一般的表
2、述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表方式，Drew为了和下面要介绍的 A* 算法和 D* 算法表述一致，这里均采用OPEN,CLOSE表的方式。 其采用的是贪心法的算法策略 大概过程： 创建两个表，OPEN, CLOSE。 OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。 1 访问路网中距离起始点最近且没有被检查过的点，把这个点放入OPEN组中等待检查。 2 从OPEN表中找出距起始点最近的点，找出这个点的所有子节点，把这个点放到CLOSE表中。 3 遍历考察这个点的子节点。求出这些子节点距起始点的距离值，放子节点到OPEN表
3、中。 4 重复第2和第3步,直到OPEN表为空，或找到目标点。编辑本段算法实现 #include #define MaxNum 765432100 using namespace std; ifstream fin(Dijkstra.in); ofstream fout(Dijkstra.out); int Map501501; bool is_arrived501; int Dist501,From501,Stack501; int p,q,k,Path,Source,Vertex,Temp,SetCard; int FindMin() int p,Temp=0,Minm=MaxNum; f
4、or(p=1;p=Vertex;p+) if (Distp Source Vertex; for(p=1;p=Vertex;p+) for(q=1;q Mappq; if (Mappq=0) Mappq=MaxNum; for(p=1;p=Vertex;p+) Distp=MapSourcep; if (Distp!=MaxNum) Fromp=Source; else Fromp=p; is_arrivedSource=true; SetCard=1; do Temp=FindMin(); if (Temp!=0) SetCard=SetCard+1; is_arrivedTemp=true
5、; for(p=1;pDistTemp+MapTempp)&(!is_arrivedp) Distp=DistTemp+MapTempp; Fromp=Temp; else break; while (SetCard!=Vertex); for(p=1;p=Vertex;p+) if(p!=Source) fout =n; fout Source: Source nTarget: p n; if (Distp=MaxNum) fout Distance: Infinityn; fout Path:No Way!; else fout Distance: Distp n; k=1; Path=p
6、; while (FromPath!=Path) Stackk=Path; Path=FromPath; k=k+1; fout Path: =1;q-) fout Stackq; fout 1 = = Source:2 Target:3 Distance:25 Path:2-3 = = Source:2 Target:4 Distance:50 Path:2-1-4 = = Source:2 Target:5 Distance:50 Path:2-3-5 = = Source:2 Target:6 Distance:60 Path:2-3-5-6 = = Source:2 Target:7
7、Distance:Infinity Path:No Way! = 示例程序及相关子程序： void Dijkstra(int n,int Distance,int iPath) int MinDis,u; int i,j; /从邻接矩阵复制第n个顶点可以走出的路线，就是复制第n行到Distance for(i=0;iVerNum;i+) Distance=Arcn,i; Visited=0; /第n个顶点被访问，因为第n个顶点是开始点 Visitedn=1; /找到该顶点能到其他顶点的路线、并且不是开始的顶点n、以前也没走过。 /相当于寻找u点，这个点不是开始点n for(i=0;iVerNu
8、m;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，VerN
9、um。 /如果有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，以后再找其他路，这个路可能别利用到。例如V3 for(j=0;jVerNum;j+) if(Visitedj=0&Arcu,jNo&u!= j) if (Distanceu + Arcu,j) = Distancej) Distancej = Distanceu + Arcu, j; Visitedj=0; iPathj = u; /辅助函数 void Prim() int i,m,n=0; for(i=0;i0) if(m=MinAdjNode(n)!=-1) Tn.Nodes.Add(Tm); n=m; Visitedn+; else n=MinNode(0); if(n0) TMin2.Nodes.Add(TMin1); Visitedn+; listBox1.Items.Add (Vn); treeV
