Dijkstra最短路径算法课程设计.doc

二、Dijkstra最短路径算法 利用matlab软件实现Dijkstra最短路径算法 要求： 输入节点数量，随机产生网孔型（不完全网状网）网络拓扑（随机产生每条链路的度量） 计算并画出任意两点之间的最短路径，以及以任一点为根的最短路径树。 设计过程 一、 Dijkstra算法 首先，引进一个辅助向量D，它的每个分量D表示当前所找到的从始点v到每个终点vi的最短路径的长度。如D[3]=2表示从始点v到终点3的路径相对最小长度为2。这里强调相对就是说在算法过程中D的值是在不断逼近最终结果但在过程中不一定就等于最短路径长度。它的初始状态为：若从v到vi直接相连，则D为之间的直接权值；否则置D为∞。显然，长度为 D[j]=Min{D | vi∈V} 的路径就是从v出发的长度最短的一条最短路径。此路径为(v,vj)。假设该次短路径的终点是vk，则这条路径或者是(v,vk)，或者是(v,vj,vk)。它的长度或者是从v到vk的弧上的权值，或者是D[j]和从vj到vk的弧上的权值之和。 一般情况下，假设S为已求得最短路径的终点的集合，则可证明：下一条最短路径（设其终点为X）或者是弧(v,x)，或者是中间只经过S中的顶点而最后到达顶点X的路径。因此，下一条长度次短的最短路径的长度必是D[j]=Min{D | vi∈V-S} 其中，D或者是弧(v,vi)上的权值，或者是D[k](vk∈S)和弧(vk,vi)上的权值之和。 随机产生网络拓扑，随机产生两点之间的度量，若两点直接相连，给出一个随机数（在此随机取从1到20之间的某一个数）。 二、 程序设计 %Dijkstra/最短路径算法 %输入结点数量，随机产生网孔型（不完全网状网）网络拓扑（随机产生每条链路的度量）。 clear all N=6 ;%输入结点的数量 net=zeros(N,N); for i=1:N for j=1:N net(i,j)=randint(1,1,10);%随机产生每条链路的度量； end end for i=1:N net(i,i)=0;end m=randint(1,1,N*(N-1)/2); for k=1:m i=randint(1,1,(N-1)); j=randint(1,1,(N-1)); net((i+1),(j+1))=Inf; end net=net+net; neigh=zeros(N,N); for i=1:N for j=1:N if(net(i,j)==inf) neigh(i,j)=0; else neigh(i,j)=net(i,j); end end end netplot(neigh);title(随机产生网孔型网络拓扑) %dijkstra 算法求任意两点之间的最短路径，以及任一点为根的最短路径树 %%% s=1;e=3;%s 根节点；e 终结点，可以随便选取 %%% n=size(net,1); % 邻接矩阵的行数n D=net(s,:); % 邻接矩阵始结点行数据，也就是从s结点到其他结点的直接距离 path=[]; % 路径初始化 visit=ones(1,n); % 结点的可访问性 visit(s)=0; % 已经加入的点不可再访问，初始化的源节点不可访问 parent=zeros(1,n); % 经过的点 % the shortest distance for i=1:n-1 %循环n-1次 temp=zeros(1,n); %临时存储 count=0; for j=1:n if visit(j) temp=[temp(1:count) D(j)]; else temp=[temp(1:count) inf];%到自身距离定义为无穷 end count=count+1; end [value,index]=min(temp);%对每一次循环得到从始点到其它结点最短距离 j=index; visit(j)=0; %j为temp中最短距离的坐标，即 for k=1:n if D(k)D(j)+net(j,k)%如果经过另一个结点到所求结点的更短距离，则用此距离替换原数据 D(k)=D(j)+net(j,k);