road1.m
上传用户:hbxtsdjs
上传日期:2022-04-11
资源大小:1594k
文件大小:1k
源码类别:

电子书籍

开发平台:

C/C++

  1. w=[0 2 1 8 inf inf inf inf;2 0 inf 6 1 inf inf inf;1 inf 0 7 inf inf 9 inf;...
  2.       8 6 7 0 5 1 2 inf;inf 1 inf 5 0 3 inf 9;inf inf inf 1 3 0 4 6;...
  3.       inf inf 9 2 inf 4 0 3;inf inf inf inf 9 6 3 0]
  4.    n=size(w,1);
  5.    w1=w(1,:);
  6.    
  7.    %赋初值
  8.    for i=1:n
  9.       l(i)=w1(i);
  10.       z(i)=1;
  11.    end
  12.    s=[];
  13.    s(1)=1;
  14.    u=s(1);
  15.    k=1
  16.    l
  17.    z
  18.    
  19. while k<n
  20.    % 更新 l(v) 和 z(v)
  21.    for i=1:n
  22.       for j=1:k
  23.       if i~=s(j) 
  24.          if l(i)>l(u)+w(u,i)
  25.             l(i)=l(u)+w(u,i);
  26.             z(i)=u;
  27.          end
  28.       end
  29.       end
  30.    end
  31.    l
  32.    z
  33.    
  34.    %求v*
  35.    ll=l;
  36.    for i=1:n
  37.       for j=1:k
  38.          if i~=s(j)
  39.             ll(i)=ll(i);
  40.          else 
  41.             ll(i)=inf;
  42.          end
  43.       end
  44.    end
  45.    
  46.    lv=inf;
  47.    for i=1:n
  48.       if ll(i)<lv
  49.          lv=ll(i);
  50.          v=i;
  51.       end
  52.    end     
  53.    lv
  54.    v
  55.    
  56.   s(k+1)=v
  57.   k=k+1
  58.   u=s(k)
  59.   
  60. end
  61. l
  62. z
  63.