• 大小: 944B
    文件类型: .rar
    金币: 1
    下载: 0 次
    发布日期: 2021-05-16
  • 语言: Matlab
  • 标签: Matlab  实例  

资源简介

Dijkstra算法的Matlab程序,用于求各点之间的最短路距离。该程序解决了一个有九个点的无向图中求任意两点之间最短路距离的例子。程序中的每一步都有详细说明。

资源截图

代码片段和文件信息

%Dijkstra最短路算法Matlab程序用于求从各点之间的最短路距离
%D为邻接矩阵需要输入
%d为s到其它各点最短距离
%pre记载了最短路径生成路线
clear all
clc
D=[0 6 inf inf 5 6 inf 5 inf
    6 0 9 inf inf 9 inf 3 inf
    inf 9 0 7 inf inf 4 inf inf
    inf inf 7 0 6 4 6 inf 3
    5 inf inf 6 0 5 inf inf 4
    6 9 inf 4 5 0 5 inf inf
    inf inf 4 6 inf 5 0 inf inf
    5 3 inf inf inf inf inf 0 inf
    inf inf inf 3 4 inf inf inf 0];%这是邻接矩阵
[mn]=size(D);%m行n列,这里m=n=9
E=zeros(mn);%E为任意两点间最短距离矩阵
for s=1:m
    %当s=1时,就是求1这个点到其他各个点的最短距离,同理,当s=2时,……=9时。
    d=inf.*ones(1m);%初始化
    d(1s)=0;%s点到s点的最短距离为0
    ok=zeros(1m);%初始化,用来记录已经求得最短路径的点
    pre=zeros(1m);%初始化
    while length(find(ok==1))        minD=inf;
        for k=1:m
           if ok(k)==0&&minD>d(k)
               minD=d(k);
               y=k;
           end
        end
        if minD==inf
            break;
        end
        ok(y)=1;
        for i=1:m
            if D(yi)~=inf
                alt=d(y)+D(yi);
                if alt                    d(i)=alt;
                    pre(i)=y;
                end
            end
        end
    end
   E(s:)=d;
end
E  %输出最短距离矩阵E,正确解为E =

    % [0     6    15    10     5     6    11     5     9
    % 6     0     9    13    11     9    13     3    15
    % 15     9     0     7    13     9     4    12    10
    % 10    13     7     0     6     4     6    15     3
    % 5    11    13     6     0     5    10    10     4
    % 6     9     9     4     5     0     5    11     7
    % 11    13     4     6    10     5     0    16     9
    % 5     3    12    15    10    11    16     0    14
    % 9    15    10     3     4     7     9    14     0]

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       1773  2009-10-25 23:36  xujinpeng_dijkstra\dijkstra.m

     目录          0  2009-10-25 23:39  xujinpeng_dijkstra

----------- ---------  ---------- -----  ----

                 1773                    2


评论

共有 条评论