论坛 › MATLAB论坛 › 求【图论】大神帮忙看看这个【dijkstra】编程！

小乱tx 发表于 2013-9-4 20:22

求【图论】大神帮忙看看这个【dijkstra】编程！

代码贴过来了，高额悬赏。比较着急，请各位帮帮忙吧！运行一下，成功必重谢！
n=100;           
w=ones(n)+inf;
for i =1:n
      w(i,i)=0;
end
A=100./[90 90 90 90 50 90 90 90 90;
90 90 90 90 50 50 110 110 110;
90 90 50 50 90 90 110 110 110;
50 50 90 90 50 50 50 90 50;
90 90 110 110 110 110 110 110 90;
90 90 90 90 90 90 90 90 50;
50 90 110 110 110 90 90 90 90;
50 90 90 90 90 90 50 50 50 ;
90 110 110 110 110 90 90 50 50;
110 130 130 130 130 130 130 130 130];
B=100./[90 90 110 90 90 90 110 90 90 110;
   90 90 110 50 50 90 90 90 110 90;
   50 50 110 50 50 50 50 50 110 50;
   90 50 110 90 50 90 50 50 50 50;
   90 90 110 90 90 90 90 90 50 50;
   50 90 110 90 50 90 90 90 50 130;
   50 90 90 90 90 110 90 50 50 130;
   50 90 90 90 50 110 90 90 90 130;
   90 110 90 90 50 50 50 90 90 130];
for a=0:9
for b=1:9
    w(90-a*10+b,90-a*10+b+1)=A(a+1,b);
    w(91-b*10+a,101-b*10+a)=B(b,a+1);
   end
end
w;%求得w为邻接矩阵

V =
w;
L(V(i)) = inf; L(V(1)) = 0;
S = [];
while ~ismember(V(100),S)
      U =setdiff(V,S);
      u=U( L(U)==min(L(U)) );
    S = ;
    for v = U
        if  L(u) + w(u,v) < L(v)
           L(v) = L(u) + w(u,v);
           parent(v) = u;
        end
    end
end


if parent(V(100)) ~= 0
   t = V(100); path = V(100);
   while t ~= a
       p = parent(t);
       path = ;
       t = p;
   end
end
L, path
完
现在卡在

Error using ==> plus
Matrix dimensions must agree.

Error in ==> a1 at 52
        if  L(u) + w(u,v) < L(v)
L(u)应该是一个数啊，为什么不能加？！

madio 发表于 2013-9-4 20:22

n=100;           
w=ones(n)+inf;
for i =1:n
      w(i,i)=0;
end
A=100./[90 90 90 90 50 90 90 90 90;
90 90 90 90 50 50 110 110 110;
90 90 50 50 90 90 110 110 110;
50 50 90 90 50 50 50 90 50;
90 90 110 110 110 110 110 110 90;
90 90 90 90 90 90 90 90 50;
50 90 110 110 110 90 90 90 90;
50 90 90 90 90 90 50 50 50 ;
90 110 110 110 110 90 90 50 50;
110 130 130 130 130 130 130 130 130];
B=100./[90 90 110 90 90 90 110 90 90 110;
   90 90 110 50 50 90 90 90 110 90;
   50 50 110 50 50 50 50 50 110 50;
   90 50 110 90 50 90 50 50 50 50;
   90 90 110 90 90 90 90 90 50 50;
   50 90 110 90 50 90 90 90 50 130;
   50 90 90 90 90 110 90 50 50 130;
   50 90 90 90 50 110 90 90 90 130;
   90 110 90 90 50 50 50 90 90 130];
for a=0:9
for b=1:9
    w(90-a*10+b,90-a*10+b+1)=A(a+1,b);
    w(91-b*10+a,101-b*10+a)=B(b,a+1);
   end
end
w;%求得w为邻接矩阵

V =
w;
L(V(:)) = inf; L(V(1)) = 0;
S = [];
while ~ismember(V(100),S)
      U =setdiff(V,S);
      u=U( L(U)==min(L(U)) )
    S = ;
    for v = U
        if  L(u(1)) + w(u(1),v) < L(v)
           L(v) = L(u(1)) + w(u(1),v);
           parent(v) = u(1);
        end
    end
end


if parent(V(100)) ~= 0
   t = V(100);
   path = V(100);
   while (t ~= a) && (t~=0)
       parent(t);
       p = parent(t);
       path = ;
       t = p;
   end
end
L, path改了一下，能出结果了，不知道是不是你想要的

小乱tx 发表于 2013-9-4 20:44

算了下L(u)，是个全0行向量，怎么回事？

小乱tx 发表于 2013-9-9 19:35

madio 发表于 2013-9-4 20:22 static/image/common/back.gif
改了一下，能出结果了，不知道是不是你想要的

完全正确，我的程序问题出在哪里啊？麻烦指点一下！

madio 发表于 2013-9-10 06:04

你可以按照错误去寻找，先把一些矩阵的中间结果显示出来，看看中间结果是否和你预期的一样，你会发现
L(V(i)) = inf;肯定有问题，这里的i并没有赋值，这一条可能只把某个成员的值变为inf了，与我们的预期不一致，然后改了错误继续查

小乱tx 发表于 2013-9-10 22:12

madio 发表于 2013-9-10 06:04 static/image/common/back.gif
你可以按照错误去寻找，先把一些矩阵的中间结果显示出来，看看中间结果是否和你预期的一样，你会发现
L(V( ...

多谢版主！原来问题在这！:)

查看完整版本: 求【图论】大神帮忙看看这个【dijkstra】编程！