定义G=(V,E>，定义集合S存放已经找到最短路径的顶点，集合T存放当前还未找到最短路径的顶点，即有T=V-S Dijkstra算法描述如下：
(1> 假设用带权的邻接矩阵edges来表示带权有向图，edges[i][j]表示弧 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 #define MaxNum 765432100 using namespace std。 ifstream fin(\"Dijkstra.in\">。 ofstream fout(\"Dijkstra.out\">。 int Map[501][501]。 bool is_arrived[501]。 int Dist[501],From[501],Stack[501]。 int p,q,k,Path,Source,Vertex,Temp,SetCard。 int FindMin(> { int p,Temp=0,Minm=MaxNum。 for(p=1。p<=Vertex。p++> if ((Dist[p] Minm=Dist[p]。 Temp=p。 } return Temp。 } int main(> { memset(is_arrived,0,sizeof(is_arrived>>。 fin >> Source >> Vertex。 for(p=1。p<=Vertex。p++> for(q=1。q<=Vertex。q++> { fin >> Map[p][q]。 if (Map[p][q]==0> Map[p][q]=MaxNum。 } for(p=1。p<=Vertex。p++> { Dist[p]=Map[Source][p]。 if (Dist[p]!=MaxNum> From[p]=Source。 else From[p]=p。 } is_arrived[Source]=true。 SetCard=1。 do { Temp=FindMin(>。 if (Temp!=0> { SetCard=SetCard+1。 is_arrived[Temp]=true。 for(p=1。p<=Vertex。p++> if ((Dist[p]>Dist[Temp]+Map[Temp][p]>&&(!is_arrived[p]>> { Dist[p]=Dist[Temp]+Map[Temp][p]。 From[p]=Temp。 } } else break。 } while (SetCard!=Vertex>。 for(p=1。p<=Vertex。p++> if(p!=Source> { fout << \"========================\\n\"。 fout << \"Source:\" << Source << \"\\nTarget:\" << p << '\\n'。 if (Dist[p]==MaxNum> { fout << \"Distance:\" << \"Infinity\\n\"。 fout << \"Path:No Way!\"。 } else { fout << \"Distance:\" << Dist[p] << '\\n'。 k=1。 Path=p。 while (From[Path]!=Path> { Stack[k]=Path。 Path=From[Path]。 k=k+1。 } fout << \"Path:\" << Source。 for(q=k-1。q>=1。q--> fout << \"-->\" << Stack[q]。 } fout << \"\\n========================\\n\\n\"。 } fin.close(>。 fout.close(>。 return 0。 } Sample Input 2 7 00 20 50 30 00 00 00 20 00 25 00 00 70 00 50 25 00 40 25 50 00 30 00 40 00 55 00 00 00 00 25 55 00 10 00 00 70 50 00 10 00 00 00 00 00 00 00 00 00 Sample Output ======================== Source:2 Target:1 Distance:20 Path:2-->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 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。i Distance=Arc[n,i]。 Visited=0。 }//第n个顶点被访问，因为第n个顶点是开始点 Visited[n]=1。 //找到该顶点能到其他顶点的路线、并且不是开始的顶点n、以前也没走过。 //相当于寻找u点，这个点不是开始点n for(i=0。i for(j=0。j if(Visited[j] == 0&&(Distance[j] MinDis=Distance[j]。 u=j。 } //如范例P1871图G6，Distance=[No,No,10,No,30,100]，第一次找就是V2，所以u=2 //找完了，MinDis等于不连接，则返回。这种情况类似V5。 if(MinDis==No> return 。 //确立第u个顶点将被使用，相当于Arc[v,u]+Arc[u,w]中的第u顶点。 Visited[u]=1。 //寻找第u个顶点到其他所有顶点的最小路，实际就是找Arc[u,j]、j取值在[0，Ve rNum]。 //如果有Arc[i,u]+Arc[u,j] //同理：对新找出的路线，要设置Visited[j]=0，以后再找其他路，这个路可能别利用到。例如V3 for(j=0。j if(Visited[j]==0&&Arc[u,j] if ((Distance[u] + Arc[u,j]> <= Distance[j]> { Distance[j] = Distance[u] + Arc[u, j]。 Visited[j]=0。 iPath[j] = u。 } } } } //辅助函数 void Prim(> { int i,m,n=0。 for(i=0。i Visited=0。 T=new TreeNode(>。 T.Text =V。 } Visited[n]++。 listBox1.Items.Add (V[n]>。 while(Visit(>>0> { if((m=MinAdjNode(n>>!=-1> { T[n].Nodes.Add(T[m]>。 n=m。 Visited[n]++。 } else { n=MinNode(0>。 if(n>0> T[Min2].Nodes.Add(T[Min1]>。 Visited[n]++。 } listBox1.Items.Add (V[n]>。 } treeView1.Nodes.Add(T[0]>。 } void TopoSort(> { int i,n。 listBox1.Items.Clear(>。 Stack S=new Stack(>。 for(i=0。i for(i=VerNum-1。i>=0。i--> if(InDegree(i>==0> { S.Push(i>。 Visited++。 } while(S.Count!=0> { n=(int >S.Pop(>。 listBox1.Items.Add (V[n]>。 ClearLink(n>。 for(i=VerNum-1。i>=0。i--> if(Visited==0&&InDegree(i>==0> { S.Push(i>。 Visited++。 } } } void AOETrave(int n,TreeNode TR,int w> { int i,w0。 if(OutDegree(n>==0> return。 for(i=0。i listBox1.Items.Add (V+\"\\"+(w+w0>.ToString(>+\"\\"+i.ToString(>+\"\\"+n.ToStri ng(>>。 TreeNode T1=new TreeNode(>。 T1.Text =V+\" [W=\"+(w+w0>.ToString(>+\"]\"。 TR.Nodes.Add(T1>。 AOETrave(i,T1,w+w0>。 } } void AOE(> { int i,w=0,m=1。 TreeNode T1=new TreeNode(>。 for(i=0。i Visited=0。 } T1.Text =V[0]。 listBox1.Items.Add (\"双亲表示法显示这个生成树：\">。 listBox1.Items.Add (\"V\W\ID\PID\">。 for(i=0。i if((w=Arc[0,i]>!=0> { listBox1.Items.Add (V+\"\\"+w.ToString(>+\"\\"+i.ToString(>+\"\0\">。 TreeNode T2=new TreeNode(>。 T2.Text=V+\" [W=\"+w.ToString(>+\"]\"。 AOETrave(i,T2,w>。 T1.Nodes.Add (T2>。 listBox1.Items.Add(\"\\树\"+m.ToString(>>。 m++。 } } treeView1.Nodes.Clear(>。 treeView1.Nodes.Add (T1>。 } int IsZero(> { int i。 for(i=0。i int LineIsZero(int n> { int i。 for(i=0。i void DepthTraverse(> { int i,m。 for(i=0。i Visited=0。 T=new TreeNode(>。 T.Text =V。 R=0。 } while((m=IsZero(>>>=0> { if(Visited[m]==0> { listBox1.Items.Add (V[m]>。 R[m]=1。 } Visited[m]++。 DTrave(m>。 } for(i=0。i treeView1.Nodes.Add (T>。 } } void DTrave(int n> { int i。 if (LineIsZero(n><0> return。 for(i=VerNum-1。i>=0。i--> if(Arc[n,i]!=0> { Arc[n,i]=0。 Arc[i,n]=0。 if(Visited==0> { listBox1.Items.Add (V>。 T[n].Nodes.Add (T>。 R=0。 } Visited++。 DTrave(i>。 } } void BreadthTraverse(> { int i,m。 for(i=0。i Visited=0。 T=new TreeNode(>。 T.Text =V。 R=0。 } while((m=IsZero(>>>=0> { if(Visited[m]==0> { listBox1.Items.Add (V[m]>。 R[m]=1。 } Visited[m]++。 BTrave(m>。 } for(i=0。i treeView1.Nodes.Add (T>。 } } void BTrave(int n> { int i。 Queue Q=new Queue(>。 Q.Enqueue(n>。 while(Q.Count!=0> { for(i=0。i if(Arc[n,i]!=0> { Arc[n,i]=0。 Arc[i,n]=0。 if(Visited==0> { listBox1.Items.Add(V>。 T[n].Nodes.Add (T>。 R=0。 } Visited++。 Q.Enqueue(i>。 } } n=(int >Q.Dequeue(>。 } } int MinNode(int vn> { int i,j,n,m,Min=No。 n=-1。m=-1。 for (i=vn。i if(Arc[i,j]!=No&&Arc[i,j] Min=Arc[i,j]。n=i。m=j。 } Min1=n。Min2=m。 return n。 } int MinAdjNode(int n> { int i,Min,m。 Min=No。m=-1。 for(i=0。i if(Arc[n,i]!=No&&Visited==0&&Min>Arc[n,i]&&Visited[n]==1> { Min=Arc[n,i]。m=i。 } return m。 } int Visit(> { int i,s=0。 for(i=0。i [编辑本段] dijkstra算法的Pascal实现： program dijkstra。 var a:array[1..100,1..100]of integer。 flag:array[1..100]of boolean。 w,x,n,i,j,min,minn:integer。 begin readln(n>。 for i:=1 to n do begin for j:=1 to n do read(a[i,j]>。 readln。 end。 fillchar(flag,sizeof(flag>,false>。 flag[1]:=true。 minn:=1。 for x:=2 to n do begin min:=32767。 for i:=2 to n do if (a[1,i] begin min:=a[1,i]。 minn:=i。 end。 flag[minn]:=true。 for j:=1 to n do if (j<>minn> and (a[1,minn]+a[minn,j] for i:=1 to n do write(a[1,i],' '>。 end. 4 0 100 30 999 100 0 99 10 30 99 0 99 999 10 99 0 程序输出：0 100 30 110 dijkstra算法的MATLAB实现： clear。 clc。 M=10000。 a(1,:>=[0,50,M,40,25,10]。 a(2,:>=[zeros(1,2>,15,20,M,25]。 a(3,:>=[zeros(1,3>,10,20,M]。 a(4,:>=[zeros(1,4>,10,25]。 a(5,:>=[zeros(1,5>,55]。 a(6,:>=zeros(1,6>。 a=a+a'。 pb(1:length(a>>=0。pb(i>=1。index1=1。index2=ones(1,length(a>>。 d(1:length(a>>=M。d(i>=0。temp=1。 while sum(pb> d(tb>=min(d(tb>,d(temp>+a(temp,tb>>。 tmpb=find(d(tb>==min(d(tb>>>。 temp=tb(tmpb(i>>。 pb(temp>=1。 index1=[index1,temp]。 index=index1(find(d(index1>==d(temp>-a(temp,index1>>>。 if length(index>>=2 index=index(1>。 end index2(temp>=index。 end d, index1, index2 matlab编程 function [s,d]=minroute(i,m,w,opt> % 图与网络论中求最短路径的dijkstra算法M函数 % 格式[s,d]=minroute(i,m,w,opt> if nargin<4,opt=0。end dd=[]。tt=[]。ss=[]。ss(1,1>=i。v=1:m。v(i>=[]。 dd=[0。i]。kk=2。[mdd,ndd]=size(dd>。 while~isempty(v> [tmpd,j]=min(w(i,v>>。tmpj=v(j>。 for k=2:ndd [tmp2,jj]=min(dd(1,k>+w(dd(2,k>,v>>。 tmp2=v(jj>。tt(k-1,:>=[tmp1,tmp2,jj]。 end。 tmp=[tmpd,tmpj,j。tt]。[tmp3,tmp4]=min(tmp(。,1>>。 if tmp3==tmpd ss(1:2,kk>=[i。tmp(tmp4,2>]。 else,tmp5=find(ss(:,tmp4>~=0>。tmp6=length(tmp5>。 if dd(2,tmp4>=ss(tmp6,tmp4> ss(1:tmp6+1,kk>=[ss(tmp5,tmp4>。tmp(tmp4,2>]。 else,ss(1:3,kk>=[i。dd(2,tmp4>。tmp(tmp4,2>]。 end。end dd=[dd,[tmp3,tmp(tmp4,2>]]。v(tmp(tmp4,3>>=[]。 [mdd,ndd]=size(dd>。kk=kk+1。 end。 if opt==1 [tmp,t]=sort(dd(2,:>>。s=ss(:t>。d=dd(1,t>。 else,s=ss。d=dd(1,:>。 end 字号：大 中 小 近来在研究dijkstra算法，终于弄懂了不少，今天下午要讲课啦，上网找了好多资料，都发现讲得不怎么详细，在这里还是为了以后和我一样想上网寻找dijkstra算法的资料小朋友服务一下，把我找到的东西在这里贴一贴吧！<不想看的或不感兴趣的飘过就好了^_^简介：Dijkstra算法是由荷兰计算机科学家艾兹格·迪科斯彻发现的。算法解决的是有向图中最短路径问题。 ------------------------------------------------------------------------- 算法介绍 Dijkstra算法是由荷兰计算机科学家艾兹格·迪科斯彻发现的。算法解决的是有向图中最短路径问题。 举例来说，如果图中的顶点表示城市，而边上的权重表示著城市间开车行经的距离。 Dijkstra算法可以用来找到两个城市之间的最短路径。 Dijkstra算法的输入包含了一个有权重的有向图G，以及G中的一个来源顶点S。 我们以V表示G中所有顶点的集合。 每一个图中的边，都是两个顶点所形成的有序元素对。(u,v>表示从顶点u到v有路径相连。 我们以E所有边的集合，而边的权重则由权重函数w: E → [0, ∞]定义。 因此，w(u,v>就是从顶点u到顶点v的非负花费值(cost>。 边的花费可以想像成两个顶点之间的距离。任两点间路径的花费值，就是该路径上所有边的花费值总和。 已知有V中有顶点s及t，Dijkstra算法可以找到s到t的最低花费路径(i.e. 最短路径>。 这个算法也可以在一个图中，找到从一个顶点s到任何其他顶点的最短路径。 算法一般流程图： 例：输入起点，终点，求其最短路径？ 下面是Dijkstra 算法： 基本思想是：设置一个顶点的集合s，并不断地扩充这个集合，一个顶点属于集合s当且仅当从源点到该点的路径已求出。开始时s中仅有源点，并且调整非s中点的最短路径长度，找当前最短路径点，将其加入到集合s，直到终点在s中。 具体程序实现： program zudlouj。 const n=6。max=10000 。 cost:array[1..6,1..6] of real=((0,50,10,max,45,max>,(max,0 ,15,max,10,max>,(20,max,0,15,max,max>,(max,20,max,0,35,max>,( max,max,max,30,0,max>,(max,max,max,3,max,0>>。{连通关系,连通路径长度，不连通则赋值为max} var dist:array[1..n] of real。 {起点到当前点的最短路径} path,p:array[1..n] of 1..n。{path[i]:记录以i为终点的到i点能取得最短路径的起点} first,tail,u:1..n。{起点与终点} s:set of 1..n。{存储已走过的点} i,j,y,m:integer。 min:real。 begin read(first,tail>。 for i:=1 to n do dist[i]:=max。{一开始所有的点都赋值为∞表示没有走过} dist[first]:=0。{起点赋值为0} s:=[first]。{起点已走过，存入s中} u:=first。{u表示当前子路径的起点位置} while u<>tail do{当子路径的起点不是终点，即还没走到终点时} begin for j:= 1 to n do if not(j in s> and (dist[u]+cost[u,j] begin dist[j]:=dist[u]+cost[u,j]。path[j]:=u end。 min:=max。 for j:=1 to n do if not(j in s> and (dist[j] writeln('mindist(',first,',',tail,'>=',dist[tail]:8:2>。 y:=tail。m:=0。 while (y<>first> do begin inc(m>。p[m]:=y。y:=path[y]。 end。{p[m]：m为终点，p[m]为起点<从后到前寻找回路径）} write('path:',first>。 for j:=m downto 1 do write('->',p[j]>。 writeln。 end. 因篇幅问题不能全部显示，请点此查看更多更全内容