Dijkstra算法.docx
《Dijkstra算法.docx》由会员分享，可在线阅读，更多相关《Dijkstra算法.docx（23页珍藏版）》请在冰点文库上搜索。
Dijkstra算法
Dijkstra算法
百科名片
Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。
主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。
Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。
目录
简介
算法描述
复杂度分析
算法实现
1.伪代码
2.输入输出格式
3.C++
4.Matlab
5.Pascal
6.测试样例
大概过程
时间复杂度
简介
Dijkstra（迪杰斯特拉）算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。
主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。
Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。
Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN,CLOSE表的方式，这里均采用永久和临时标号的方式。
注意该算法要求图中不存在负权边。
算法描述
（这里描述的是从节点1开始到各点的dijkstra算法，其中Wa->b表示a->b的边的权值，d（i）即为最短路径值）
1．置集合S={2,3,...n},数组d
（1）=0,d（i）=W1->i（1,i之间存在边）or+无穷大（1.i之间不存在边）
2．在S中，令d（j）=min{d（i）,i属于S}，令S=S-{j}，若S为空集则算法结束，否则转3
3．对全部i属于S,如果存在边j->i，那么置d（i）=min{d（i）,d（j）+Wj->i}，转2
Dijkstra算法思想为：
设G=（V,E）是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径,就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。
在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。
此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。
算法具体步骤
（1）初始时，S只包含源点，即S=，v的距离为0。
U包含除v外的其他顶点，U中顶点u距离为边上的权（若v与u有边）或∞（若u不是v的出边邻接点）。
（2）从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。
（3）以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u（uU）的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值为顶点k的距离加上边上的权。
（4）重复步骤
（2）和（3）直到所有顶点都包含在S中。
复杂度分析
Dijkstra算法的时间复杂度为O（n^2）
空间复杂度取决于存储方式，邻接矩阵为O（n^2）
算法实现
伪代码
Dijkstra算法解决了有向图G=（V,E）上带权的单源最短路经问题，但要求所有边的权值非负。
因此，我们假定对每条边（u，v）∈E，有w（u，v）≥0。
Dijkstra算法中设置了一个顶点集合S，从源点s到集合中的顶点的最终最短路径的权值均已确定。
算法反复选择具有最短路径估计的顶点u∈V-S，并将u加入到S中，对u的所有出边进行松弛。
在下面的算法实现中，用到了顶点的最小优先队列Q，排序关键字为顶点的d值。
DIJSTRA（G，w，s）
1 INITIALIZE-SINGLE-SOURCE（G，s）
2 S←Φ
3 Q←V[G]
4 whileQ≠Φ
5 douEXTRACT-MIN（Q）
6 S←S∪{u}
7 foreachvertexv∈Adj[u]
8 doRELAX（u，v，w）
输入输出格式
输入格式:
第1行:
一个数n，代表有n个节点
第2-n+1行:
每行n个数，代表图的邻接矩阵，没有边相连为-1
输出格式:
第1行:
n-1个数，分别是1号节点到2-n号节点的最短路径
C++
#include
#include
usingnamespacestd;
constintMaxNum=1000000;//边权最大值
intn;//节点数目
intdist[501];//到节点1的最短路径值
boolstate[501];//节点被搜索过状态指示
intdata[501][501];//邻接矩阵
//查找权值最小的节点
intfindmin（）
{
intminnode=0,min=MaxNum;
for（inti=1;i<=n;i++）
if（（dist[i]state[i]））
{
min=dist[i];
minnode=i;
}
returnminnode;
}
intmain（）
{
ifstreamin（"dijkstra.in"）;
ofstreamout（"dijkstra.out"）;
memset（state,0,sizeof（state））;
in>>n;
for（intp=1;p<=n;p++）
for（intq=1;q<=n;q++）
{
in>>data[p][q];
if（data[p][q]==0）data[p][q]=MaxNum;
}
//初始化
for（inti=1;i<=n;i++）
dist[i]=data[1][i];
state[1]=true;
intdone=1;
while（done {
intnode=findmin（）;
if（node!
=0）
{
done++;//找到的点的数目加1
state[node]=true;//标记已经找到了从节点1到节点node的最短路径
for（inti=1;i<=n;i++）//更新还没有找到的点的路径值
if（（dist[i]>dist[node]+data[node][i]）&&（!
state[i]））
dist[i]=dist[node]+data[node][i];
}
elsebreak;
}
for（intk=1;k<=n;k++）
{
if（dist[k]==MaxNum）
out<<-1;
else
out< if（k==n）
out< else
out<<"";
}
in.close（）;
out.close（）;
return0;
}
Matlab
functionDijkstra（w,start,MAX）
%w为此图的距离矩阵
%start为起始端点下标（从1开始）
%MAX是数据输入时的∞的实际值
%2011年6月19日17:
02:
03
len=length（w）;
flag=zeros（len,2）;
index=zeros（1,len）;
index
（1）=start;
%根据路由类型初始化路由表
R=ones（len,2）*MAX;
R（1,1）=0;
R（1,2）=start;
port=zeros（1,len）;
port（start）=0;
%处理端点有权的问题
fori=1:
len
tmp=w（i,i）/2;
iftmp~=0
w（i,:
）=w（i,:
）+tmp;
w（:
i）=w（:
i）+tmp;
flag（i,1）=1;%表示端i点有权值
flag（i,2）=tmp;%存储端点权值的一半
end
w（i,i）=MAX;
end
s=sprintf（'\tv%d',1:
len）;
s_tmp=sprintf（'\t|%s\t%s\t','置定端','距离'）;
s=strcat（s,s_tmp）;
s_tmp=sprintf（'%s\t','路由'）;
s=strcat（s,s_tmp）;
s_tmp=sprintf（'\n----------------------------------------------------\n\t0'）;
s=strcat（s,s_tmp）;
fori=1:
len-1
s_tmp=sprintf（'\t∞'）;
s=strcat（s,s_tmp）;
end
s_tmp=sprintf（'\t|\t%d\t%4.1f\t%d',start,0,start）;
s=strcat（s,s_tmp）;
disp（s）;
%Dijkstra算法具体实现过程
count=1;
whilecount s='';
N=MAX;%暂存每次距离比较的较大值
x=1;%暂存每次距离比较的较大值的下标
fori=1:
len
ifisempty（find（index==i,1））%将没有在置定点的i值跳过
continue
end
forj=1:
len
if~isempty（find（index==j,1））%将在置定点的j值跳过
continue
else
port（j）=R（i,1）+w（i,j）;%新距离
end
ifport（j） R（j,1）=port（j）;
R（j,2）=i;
else
port（j）=R（j,1）;
end
ifport（j） N=port（j）;
x=j;
end
end
end
fork=1:
len%输出格式设置（考虑端权值）
ifisempty（find（index==k,1））
ifport（k）==MAX
s_tmp=sprintf（'\t%s','∞'）;
else
ifflag（k,1）
port（k）=port（k）-flag（k,2）;
end
s_tmp=sprintf（'\t%2.1f',port（k））;
end
else
s_tmp=sprintf（'\t%s','_'）;
end
s=strcat（s,s_tmp）;
end
ifflag（x,1）
R（x,1）=R（x,1）-flag（x,2）;
end
s_tmp=sprintf（'\t|\t%d\t%4.1f\t%d',x,R（x,1）,R（x,2））;
s=strcat（s,s_tmp）;
disp（s）;
%为下次的循环设置条件——更新置定点列表+count加1
count=count+1;
index（count）=x;
end
end
示例：
输入：
b=[
0,9.2,1.1,3.5,100,100;
1.3,0,4.7,100,7.2,100;
2.5,100,0,100,1.8,100;
100,100,5.3,0,2.4,7.5;
100,6.4,2.2,8.9,0,5.1;
7.7,100,2.7,100,2.1,0
];
Dijkstra（b,1,100）
Pascal
programdijkstra;
var
state:
array[1..100]ofboolean;
data:
array[1..100,1..100]oflongint;
n,i,j,k,min,node:
longint;
begin
assign（input,'dijkstra.in'）;
assign（output,'dijkstra.out'）;
reset（input）;
rewrite（output）;
fillchar（data,sizeof（data）,0）;
fillchar（state,sizeof（state）,0）;
readln（n）;
fori:
=1tondo
forj:
=1tondo
begin
read（data[i,j]）;
ifdata[i,j]=0thendata[i,j]:
=maxint;
end;
state[1]:
=true;
fork:
=2tondo
begin
min:
=maxint;
{查找权值最小的点为node}
node:
=1;
fori:
=2tondo
if（data[1,i] begin
min:
=data[1,i];
node:
=i;
end;
{更新其他各点的权值}
state[node]:
=true;
forj:
=1tondo
if（data[1,node]+data[node,j] data[1,j]:
=data[1,node]+data[node,j];
end;
fori:
=1ton-1do
ifdata[1,i]<>maxintthen
write（data[1,i],''）
else
write（-1,''）;
writeln（data[1,n]）;
close（input）;
close（output）;
end.
测试样例
SampleInput
7
00205030000000
20002500007000
50250040255000
30004000550000
00002555001000
00705000100000
00000000000000
SampleOutput
-12045307080-1
大概过程
创建两个表，OPEN,CLOSE。
OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。
1．访问路网中里起始点最近且没有被检查过的点，把这个点放入OPEN组中等待检查。
2．从OPEN表中找出距起始点最近的点，找出这个点的所有子节点，把这个点放到CLOSE表中。
3．遍历考察这个点的子节点。
求出这些子节点距起始点的距离值，放子节点到OPEN表中。
4．重复2，3，步。
直到OPEN表为空，或找到目标点。
/*Dijkstra.c
Copyright（c）2002,2006byctu_85
AllRightsReserved.
*/
#include"stdio.h"
#include"malloc.h"
#definemaxium32767
#definemaxver9/*definesthemaxnumberofvertexswhichtheprogrammcanhandle*/
#defineOK1
structPoint
{
charvertex【3】;
structLink*work;
structPoint*next;
};
structLink
{
charvertex【3】;
intvalue;
structLink*next;
};
structTable/*theworkbannchofthealgorithm*/
{
intcost;
intKnown;
charvertex【3】;
charpath【3】;
structTable*next;
};
intDijkstra（structPoint*,structTable*）;
intPrintTable（int,structTable*）;
intPrintPath（int,structTable*,structTable*）;
structTable*CreateTable（int,int）;
structPoint*FindSmallest（structTable*,structPoint*）;/*Findthevertexwhichhasthesmallestvalueresideinthetable*/
intmain（）
{
inti,j,num,temp,val;
charc;
structPoint*poinpre,*poinhead,*poin;
structLink*linpre,*linhead,*lin;
structTable*tabhead;
poinpre=poinhead=poin=（structPoint*）malloc（sizeof（structPoint））;
poin->next=NULL;
poin->work=NULL;
restart:
printf（"Notice:
ifyouwannatoinputavertex,youmustusetheformatofnumber!
\n"）;
printf（"Pleaseinputthenumberofpoints:
\n"）;
scanf（"%d",&num）;
if（num>maxver||num<1||num%1!
=0）
{
printf（"\nNumberofpointsexception!
"）;
gotorestart;
}
for（i=0;i{
printf（"Pleaseinputthepointsnexttopoint%d,endwith0:
\n",i+1）;
poin=（structPoint*）malloc（sizeof（structPoint））;
poinpre->next=poin;
poin->vertex【0】='v';
poin->vertex【1】='0'+i+1;
poin->vertex【2】='\0';
linpre=lin=poin->work;
linpre->next=NULL;
for（j=0;j{
printf（"Thenumberofthe%dthvertexlinkedtovertex%d:
",j+1,i+1）;
scanf（"%d",&temp）;
if（temp==0）
{
lin->next=NULL;
break;
}
else
{
lin=（structLink*）malloc（sizeof（structLink））;
linpre->next=lin;
lin->vertex【0】='v';
lin->vertex【1】='0'+temp;
lin->vertex【2】='\0';
printf（"Pleaseinputthevaluebetwixt%dthpointtowards%dthpoint:
",i+1,temp）;
scanf（"%d",&val）;
lin->value=val;
linpre=linpre->next;
lin->next=NULL;
}
}
poinpre=poinpre->next;
poin->next=NULL;
}
printf（"PleaseenterthevertexwhereDijkstraalgorithmstarts:
\n"）;
scanf（"%d",&temp）;
tabhead=CreateTable（temp,num）;
Dijkstra（poinhead,tabhead）;
PrintTable（temp,tabhead）;
returnOK;
}
structTable*CreateTable（intvertex,inttotal）
{
structTable*head,*pre,*p;
inti;
head=pre=p=（structTable*）malloc（sizeof（structTable））;
p->next=NULL;
for（i=0;i{
p=（structTable*）malloc（sizeof（structTable））;
pre->next=p;
if（i+1==vertex）
{
p->vertex【0】='v';
p->vertex【1】='0'+i+1;
p->vertex【2】='\0';
p->
升级会员 