求利用matlab求从A到O的最短路径的程序代码~~~

发布网友发布时间：2022-04-24 01:58

共1个回答

热心网友时间：2023-10-20 10:56

function R=main_Dj()
clc;clear
G=[1 2 5;1 4 1;2 3 1;2 4 6;2 5 5.8;2 6 5.7;2 7 5.6;3 7 2; 3 11 1.5; 3 12 4;...
    4 5 0.5;4 8 3; 5 6 1;5 9 3;6 7 0.6;6 10 2.5; 7 11 2.7;8 9 1;8 12 6;...
    9 10 1.5;9 12 5;10 11 0.5;10 12 4;11 12 3];
opt=0;
route=sroute(G,opt);
R=[];
r=route(3,end);
R=[r,R];
while r~=1
  r=route(3,r);
  R=[r,R];
end
R=char(R+64);
R=[R,'O'];

end
function route=sroute(G,opt)
% 求图的最短路的Dijkstra算法，规定1是起点
% G是给定图的邻接矩阵或弧表矩阵，程序能够自动识别
% 当opt=0（或缺省）时求无向图的最短路，opt=1时求有向图的最短路
% d——标记最短距离
% route是一个矩阵，第一行标记顶点，第2行标记1到该点的最短距离，
% 第3行标记最短路上该点的先驱顶点
if (nargin==1) opt=0; end
while 1      % 此循环自动识别或由弧表矩阵生成邻接矩阵
   if G(1,1)==0
      A=G;
      n=size(A,1);
      M=sum(sum(A));break
   else
      e=G;
      n=max([e(:,1);e(:,2)]);          % 顶点数
      m=size(e,1);                     % 边数
      M=sum(e(:,3));                   % 代表无穷大
      A=M*ones(n,n);
      for k=1:m
          A(e(k,1),e(k,2))=e(k,3);
          if opt==0
               A(e(k,2),e(k,1))=e(k,3); % 形成无向图的邻接矩阵
          end
      end
      A=A-M*eye(n);                      % 形成图的邻接矩阵
   end
   break
end
pb(1:length(A))=0;pb(1)=1;               % 永久标号点记为1
index1=1;                                % 依次记录永久标号顶点
index2=ones(1,length(A));                % 标记最短路上各点的先驱顶点
d(1:length(A))=M;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];                 % 记录新永久标号点
   index=index1(find(d(index1)==d(temp)-A(index1,temp)')); % 确定前驱顶点
   if length(index)>=2                   % 前驱顶点多于1个时取第一个
      index=index(1);
   end
   index2(temp)=index;                   % 记录前驱顶点
end
route=[1:n; d; index2];

end

运行结果
R =

ADEFJKO
代码自己看，不解释，也别叫我解释了，很麻烦的。

热心网友时间：2023-10-20 10:56