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<fstream>

#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)&&(!is_arrived[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;

{

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 << "========================

fout << "Source:" << Source << "

Target:" << p << '

if (Dist[p]==MaxNum)

{

fout << "Distance:" << "Infinity

fout << "Path:No Way!";

}

else

{

fout << "Distance:" << Dist[p] << '

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 << "

========================

}

fin.close();

fout.close();

return 0;

}

Sample Input

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<VerNum;i++)

{

Distance=Arc[n,i];

Visited=0;

}//第n个顶点被访问，因为第n个顶点是开始点

Visited[n]=1;

//找到该顶点能到其他顶点的路线、并且不是开始的顶点n、以前也没走过。

//相当于寻找u点，这个点不是开始点n

for(i=0;i<VerNum;i++)

{

u=0;

MinDis=No;

for(j=0;j<VerNum;j++)

if(Visited[j] == 0&&(Distance[j]<MinDis))

{

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，VerNum]。

//如果有Arc[i,u]+Arc[u,j]<Arc[i,j]，则Arc[i,j]=Arc[i,u]+Arc[u,j]<Arc[i,j]

//实际中，因为Distance[]是要的结果，对于起始点确定的情况下，就是：

//如果(Distance[u] + Arc[u,j]) <= Distance[j] 则：

//Distance[j] = Distance[u] + Arc[u, j]；

//而iPath[]保存了u点的编号；

//同理：对新找出的路线，要设置Visited[j]=0，以后再找其他路，这个路可能别利用到。例如V3

for(j=0;j<VerNum;j++)

if(Visited[j]==0&&Arc[u,j]<No&&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<VerNum;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<VerNum;i++)

Visited=0;

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<VerNum;i++)

if((w0=Arc[n,i])!=0)

{

listBox1.Items.Add (V+""+(w+w0).ToString()+""+i.ToString()+""+n.ToString());

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<VerNum;i++)

{

Visited=0;

}

T1.Text =V[0];

listBox1.Items.Add ("双亲表示法显示这个生成树：");

listBox1.Items.Add ("VWIDPID");

for(i=0;i<VerNum;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<VerNum;i++)

if(LineIsZero(i)>=0) return i;

return -1;

}

int LineIsZero(int n)

{

int i;

for(i=0;i<VerNum;i++)

if (Arc[n,i]!=0) return i;

return -1;

}

void DepthTraverse()

{

int i,m;

for(i=0;i<VerNum;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<VerNum;i++)

{

if(R==1)

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<VerNum;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<VerNum;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;i<VerNum;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<VerNum;i++)

for(j=0;j<VerNum;j++)

if(Arc[i,j]!=No&&Arc[i,j]<Min&&Visited==0&&Visited[j]==1)

{

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<VerNum;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<VerNum;i++)

if(Visited==0) s++;

return s;

}

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

for j:=1 to n do

read(a[i,j]);

fillchar(flag,sizeof(flag),false);

flag[1]:=true;

minn:=1;

for x:=2 to n do

begin

min:=maxint;

for i:=2 to n do

if (a[1,i]<min)and(flag[i]=false) then

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]<a[1,j]) and(flag[j]=false) then

a[1,j]:=a[1,minn]+a[minn,j];

end;

for i:=1 to n do

write(a[1,i],' ');

end.

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)<length(a)

tb=find(pb==0);

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