1、关于最短路的 Dijkstra 算法的程序源代码! 悬赏分：150 | 解决时间： 2009-1-25 00:57 | 提问者：hraper 最好是 matlab 的！急用！哪位高手有相关的程序请发到,谢谢！最佳答案 Dijkstra 算法 Dijkstra 算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra 算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。Dijkstra 算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。Dijks
2、tra 一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE 表方式，Drew 为了和下面要介绍的 A* 算法和 D* 算法表述一致，这里均采用 OPEN,CLOSE 表的方式。其采用的是贪心法的算法策略大概过程：创建两个表，OPEN, CLOSE。OPEN 表保存所有已生成而未考察的节点，CLOSED 表中记录已访问过的节点。1 访问路网中距离起始点最近且没有被检查过的点，把这个点放入 OPEN组中等待检查。2 从 OPEN 表中找出距起始点最近的点，找出这个点的所有子节点，把这个点放到 CLOSE 表中。3 遍历考察这个点的子节点。求出这些子节点距起始点的距离
3、值，放子节点到 OPEN 表中。4 重复第 2 和第 3 步,直到 OPEN 表为空，或找到目标点。编辑本段算法实现#include#define MaxNum 765432100using 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,Mi
4、nm=MaxNum;for(p=1;p Source Vertex;for(p=1;p Mappq;if (Mappq=0) Mappq=MaxNum;for(p=1;pDistTemp+MapTempp)Fromp=Temp;elsebreak;while (SetCard!=Vertex);for(p=1;p=1;q-)fout “ 1=Source:2Target:3Distance:25Path:23=Source:2Target:4Distance:50Path:214=Source:2Target:5Distance:50Path:235=Source:2Target:6Dista
5、nce:60Path:2356=Source:2Target:7Distance:InfinityPath:No Way!=示例程序及相关子程序：void Dijkstra(int n,int Distance,int iPath)int MinDis,u;int i,j;/从邻接矩阵复制第 n 个顶点可以走出的路线，就是复制第 n 行到 Distancefor(i=0;i0)if(m=MinAdjNode(n)!=-1)Tn.Nodes.Add(Tm); n=m;Visitedn+;elsen=MinNode(0);if(n0) TMin2.Nodes.Add(TMin1); Visited
6、n+;listBox1.Items.Add (Vn); treeView1.Nodes.Add(T0); void TopoSort()int i,n;listBox1.Items.Clear(); Stack S=new Stack();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=0Visited+;void AOETrave(i
7、nt n,TreeNode TR,int w)int i,w0;if(OutDegree(n)=0) return;for(i=0;i=0) return i;return -1;int LineIsZero(int n)int i;for(i=0;i=0)if(Visitedm=0) listBox1.Items.Add (Vm);Rm=1;Visitedm+;DTrave(m);for(i=0;i=0;i-)if(Arcn,i!=0)Arcn,i=0;Arci,n=0;if(Visited=0)listBox1.Items.Add (V);Tn.Nodes.Add (T); R=0;Visited+;DTrave(i);void BreadthTraverse()int i,m;for(i=0;i=0)if(Visitedm=0) listBox1.Items.Add (Vm);Rm=1;Visitedm+;BTrave(m);for(i=0;iVerNum;i+)if(R=1)treeView1.Nodes.Add (T); void BTrave(int n)int i;Queue Q=new Queue();Q.Enqueue(n);while(Q.Count!=0)for(i=0;iVerNum;i+)if(Arcn,i!=0)Arcn,i=0;Arci,n=0;
