数学建模社区-数学中国

标题: 求【图论】大神帮忙看看这个【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 = [1:100]
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 = [S u];
    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 = [p 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

1. n=100;           
   
2. w=ones(n)+inf;
   
3. for i =1:n
   
4.       w(i,i)=0;
   
5. end
   
6. A=100./[90 90 90 90 50 90 90 90 90;
   
7. 90 90 90 90 50 50 110 110 110;
   
8. 90 90 50 50 90 90 110 110 110;
   
9. 50 50 90 90 50 50 50 90 50;
   
10. 90 90 110 110 110 110 110 110 90;
    
11. 90 90 90 90 90 90 90 90 50;
    
12. 50 90 110 110 110 90 90 90 90;
    
13. 50 90 90 90 90 90 50 50 50 ;
    
14. 90 110 110 110 110 90 90 50 50;
    
15. 110 130 130 130 130 130 130 130 130];
    
16. B=100./[90 90 110 90 90 90 110 90 90 110;
    
17.    90 90 110 50 50 90 90 90 110 90;
    
18.    50 50 110 50 50 50 50 50 110 50;
    
19.    90 50 110 90 50 90 50 50 50 50;
    
20.    90 90 110 90 90 90 90 90 50 50;
    
21.    50 90 110 90 50 90 90 90 50 130;
    
22.    50 90 90 90 90 110 90 50 50 130;
    
23.    50 90 90 90 50 110 90 90 90 130;
    
24.    90 110 90 90 50 50 50 90 90 130];
    
25. for a=0:9
    
26. for b=1:9
    
27.     w(90-a*10+b,90-a*10+b+1)=A(a+1,b);
    
28.     w(91-b*10+a,101-b*10+a)=B(b,a+1);
    
29.    end
    
30. end
    
31. w;%求得w为邻接矩阵
    
32. 
    
33. V = [1:100]
    
34. w;
    
35. L(V(:)) = inf; L(V(1)) = 0;
    
36. S = [];
    
37. while ~ismember(V(100),S)
    
38.       U =setdiff(V,S);
    
39.       u=U( L(U)==min(L(U)) )
    
40.     S = [S u(1)];
    
41.     for v = U
    
42.         if  L(u(1)) + w(u(1),v) < L(v)
    
43.            L(v) = L(u(1)) + w(u(1),v);
    
44.            parent(v) = u(1);
    
45.         end
    
46.     end
    
47. end
    
48. 
    
49. 
    
50. if parent(V(100)) ~= 0
    
51.    t = V(100);
    
52.    path = V(100);
    
53.    while (t ~= a) && (t~=0)
    
54.        parent(t);
    
55.        p = parent(t);
    
56.        path = [p path];
    
57.        t = p;
    
58.    end
    
59. end
    
60. L, path

复制代码

改了一下，能出结果了，不知道是不是你想要的

---

作者: 小乱tx    时间: 2013-9-4 20:44
算了下L(u)，是个全0行向量，怎么回事？

---

作者: 小乱tx    时间: 2013-9-9 19:35

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

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

---

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

---

作者: 小乱tx    时间: 2013-9-10 22:12

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

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

---

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

Powered by Discuz! X2.5