迪克斯特拉算法

[复制链接]

字体大小: 正常放大

haibin969571154

1 主题	3 听众	42 积分

升级 38.95%

该用户从未签到

自我介绍: 我是一个数模的喜爱者

群组: matlab共享与进阶

群组: MATLAB讨论交流群

群组: MATLAB

群组: Matlab讨论组

电梯直达

1^#

发表于 2010-8-6 22:23 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

%最短路问题(迪克斯特拉算法)
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';
%length函数返回的是矩阵中行数和列数中较大的长度
pb(1:length(a))=0;%生成一个一行多列的0矩阵
pb(1)=1; %第一个数赋值为1
index1=1;
index2=ones(1,length(a));%生成一个一行多列的1矩阵
d(1:length(a))=M; d(1)=0; temp=1;
%sum函数为各行之和
while sum(pb)<length(a)
  tb=find(pb==0);%find函数返回的是pb矩阵中数值为0的坐标(2,3,4,5,6....)
  d(tb)=min(d(tb),d(temp)+a(temp,tb));
  tmpb=find(d(tb)==min(d(tb)));
  temp=tb(tmpb(1));
  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
迪杰斯特拉算法用于求解一个有向图（也可以是无向图，无向图是有向图的一种特例）的一个点（称之为原点）到其余各点（称之为周边点）的最短路径问题。算法构思很是巧妙（我这么认为），简直达到了“无心插柳柳成荫”的境界。算法本身并不是按照我们的思维习惯——求解从原点到第一个点的最短路径，再到第二个点的最短路径，直至最后求解完成到第n个点的最短路径，而是求解从原点出发的各有向路径的从小到大的排列（如果这个有向图中有环1-2-3-1算法岂不是永无终结之日了？？！！），但是算法最终确实得到了从原点到图中其余各点的最短路径，可以说这是个副产品，对于算法的终结条件也应该以求得了原点到图中其余各点的最短路径为宜。清楚了算法的这种巧妙构思后，理解算法本身就不是难题了。
   算法把一个图（G）中的点划分成了若干部分：
   1）：原点（v）；
   2）：所有周边点（C）；
   另外有一个辅助集合S，从v到S中的点的最短路径已经求得。S的最初状态是空集。
   这样就可以进一步划分图（G）：
   1）：原点（v）；
   2）：已求出v至其最短路径的周边点（S）；
   3）：尚未求出v至其最短路径的周边点（Other=C-S）；
   算法的主体思想：
         A、找到v——Other所有路径中的的最短路径vd=v——d（Other的一个元素）；
B、找到v——S——Other所有路径中的的最短路径vi=v——i（Other的一个元素）；
C、比较vd和vi如果vd<=vi则将d加入S且从Other中删除，否则将i加入S且从Other中删除。
重复以上步骤直至Other为空集。

我们求得的最短路径是升序排列的，那为什么下一条最短路径就存在于v——

zan