dijkstra算法的MATLAB实现258163

已经输入图的信息，运行程序，选择工作模式，输入任务信息即可得到最短路径详细信息。两种工作模式，一种为输入要途径的节点序列，且节点顺序已定，程序输出最短路径的途径节点及路径距离。第二种为输入要途径的节点序列，但节点顺序不定，程序自动寻找路径最短的任务序列，并输出相关详细信息。

clear all;
close all;
x=[10 33 40 58 70 79 100 10 40 100 10 20 40 60 70 78 100 40 70 10 25 40 55 70 90 100 10 40 70 10 21 40 70 85 100];    
y=[100 100 100 100 100 100 100 80 80 75 70 70 70 70 70 70 70  50 60 31 31 31 31 31 31 31 15 20 20 10 10 10 10 10 10];
 %xy是假设的工位的坐标点
z1=[1 1 2 3 3 4 5 5 6 7 8 9 10 11 11 12 13 13 14 15 15 16 17 18 19 20 20 21 22 22 23 24 24 25 26 27 28 29 30 31 32 33 34 ];
z2=[2 8 3 4 9 5 6 15 7 10 11 13 17 12 20 13 14 18 15 16 19 17 26 22 24 21 27 22 23 28 24 25 29 26 35 30 32 33 31 32 33 34 35];

A=inf*ones（3535）;
a=zeros（143）;
for i=1:43
 a（i）=abs（x（z1（i））-x（z2（i）））+abs（y（z1（i））-y（z2（i）））; 
end
for i=1:43
    A（z1（i）z2（i））=a（i）;
end
for i=1:35
     for j=1:35
            if i>j
                A（ij）=A（ji）;
            end
     end
end           %建立给定无向图

%选择工作模式
G=input（‘please choose one way to work: 1 （given order）2 （given points）: ‘）;
if  G==1                  %给定顺序工作方式
   o=input（‘how many points do you want to pass by ?  ‘）;   %o为输入要途径点的个数
   S=zeros（1o）;
   q=0;
   L=zeros（1o）;
   for  i=1:o
         t=input（‘please input a point: ‘）;  
         if（t<0||t>35）
             beep
             error（‘this is an error‘）
         end        %输入的数据应合法
         if  t==0
             break
         else
             S（i）=t;
             q=q+1;
         end
   end  
        if q               disp（‘warning! numbers of input is less than given‘）
               break
        end
     
        for   i=1:o
            L（i）=S（i）;
        end
else            %-----------------------------------------------------
    o=input（‘how many points do you want to input ?: ‘）;   %o为输入要途径点的个数
    S=zeros（1o）;                                    %输入节点寄存矩阵
   for  i=1:o
     t=input（‘please input a point: ‘）;             
           if  t==0
             break
           else
            S（i）=t;
           end
   end  
    s=o;
    r=1;
  while（1）   
     if s==0;
       break
     end
       r=r*s;         %确定字母排序运算的次数 
       s=s-1;
  end
 SY=zeros（ro）;      %所有可能路径的记录矩阵
 [cd]=sort（S）;      %第一步，对输入数据进行升序排序，以便于后续使用字母排序算法，c为升序矩阵
  a=1;               
  b=1;
  for b=1:o              %将排序生成的数赋给指定的矩阵，为后续dijkstra运算提供数源（SY）
      SY（ab）=c（b）;
  end
for   time=1:r-1
   for  i=o:-1:2      %以下部分为第三步，找出jk点。
       if c（i-1）          j=i-1;
         break
       end
   end                               %找出j点  
    x1=j+1;                            
    mindist1=inf;
     for   i=x1:o     
          if  c（i）c（j）    %求出比S（j）大的在S（j）后的最小值S（k）
               mindist1=c（i）;
               k=i;              
          end
     end                   %找出k点
     
     v=c（j）;               %第四步，交换jk点的值。my_swap.m函数已定义并存储
     c（j）=c（k）;
     c（k）=v;       
     m=j+1;                %第五步，将j点后所有值对调。
     n=o;
     while （m         v=c（m）;
         c（m）=c（n）;
         c（n）=v;