数学建模社区-数学中国

标题: 【新手求助】matlab Dijkstra算法求最短路径程序报错~求助！！ [打印本页]

作者: wuyuewonder 时间: 2013-9-2 00:00
标题: 【新手求助】matlab Dijkstra算法求最短路径程序报错~求助！！
原程序如下：

clc
a=zeros(100);
A=100./[90 50 50 50 90 90 50 90 90;
110 90 90 90 90 50 50 90 90;
90 90 90 110 110 110 110 110 110;
90 90 90 90 90 90 50 50 90;
50 50 90 50 90 50 50 50 90;
50 110 110 90 90 90 50 90 90;
50 90 90 90 90 50 50 90 110;
90 90 50 90 90 50 50 90 90;
90 90 50 50 50 50 110 110 90;
130 130 130 130 50 50 50 90 110];
B=100./[110 90 50 50 90 90 50 90 90 90;
130 110 90 90 90 90 50 90 90 90;
130 110 90 110 90 110 90 50 90 90;
130 110 90 110 90 110 90 50 90 90;
130 110 90 110 90 110 50 90 50 50;
130 90 90 90 90 110 50 90 50 90;
130 90 50 90 90 110 50 110 110 90;
130 50 50 90 90 110 90 110 110 90;
130 50 50 90 50 90 50 110 110 90];
for i=0:9
for  j=1:9
   a(i*10+j,i*10+j+1)=A(i+1,j);
   a((j-1)*10+i+1,(j-1)*10+i+1+10)=B(j,i+1);
end
end
for i=1:10
for j=1:10
      if i==j
         a(i,j)=0;
      end
end
end
a(find(a==0))=inf;
a;
pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a));
d(1:length(a))=inf;d(1)=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(1));
pb(temp)=1;
index1=[index1,temp];
temp2=find(d(index1)==d(temp)-a(temp,index1));
index2(temp)=index1(temp2(1));
end
d,index1,index2

运行结果：
Attempted to access temp2(1); index out of bounds because numel(temp2)=0.

Error in lu (line 47)
index2(temp)=index1(temp2(1));

即矩阵temp2(1)中没有元素。。。
但是我求解temp2的时候，即find(d(index1)==d(temp)-a(temp,index1)的时候temp2有值但同时出现了很多行的“temp2 =Empty matrix: 1-by-0”
理论上temp2中是有元素的，为什么整体运行程序总是说“numel(temp2)=0”
程序中a是邻接矩阵，并且a输出是没问题的。
之后如何用Dijkstra算法求解最短路径和具体路线？
matlab菜鸟一只，希望问题讲清楚了。。。请求大神帮忙！！！！

作者: madio 时间: 2013-9-2 08:02
编程思路不太明确，就是a(temp,index1)的下标肯定取的不对，取到了inf，如果去掉这一行
index1=[index1,temp];还可以循环两步，但是后面还是会取到inf，你仔细看看

作者: lvyanlong 时间: 2013-9-2 13:11
http://www.madio.net/forum.php?mod=viewthread&tid=164577 你看一下这里面的代码

作者: 天空和海 时间: 2013-9-3 08:27
我有迪克斯特拉的代码

欢迎光临数学建模社区-数学中国 (http://www.madio.net/)