Dijkstra最短路径算法的Matlab实现

Dijkstra最短路径算法的Matlab实现 包括最短路径的打印子程序（感觉挺有用）

%Dijkstra
clear;clc;
format compact;
%M=inf;
%%%     输入邻接矩阵a      %%%
a=inf（2424）;
a（13）=450;a（32）=80;a（34）=1150;a（45）=1100;
a（56）=202;a（67）=20;a（78）=195;a（89）=306;a（510）=1200;
a（511）=720;a（1113）=520;a（1112）=690;a（1314）=170;
a（1415）=88;a（1516）=462;a（1417）=690;a（1418）=160;
a（1819）=70;a（1820）=320;a（2021）=160;a（2122）=70;
a（2123）=290;a（2324）=30;
for i = 1:24    %针对无向图，化为对称阵
    for j = 1:24
        if（a（ij） ~= inf）
            a（ji） = a（ij）;
        end
    end
end
%%%      输入邻接矩阵a      %%%
v0=13;%输入源点

n = length（a）;
dist = inf（1n）;%初始距离设为无穷大
path = zeros（1n）-1;%初始值设为-1，-1表示不可达
s=false（1n）;%s（i）=1表示i点在S中logic比double节约空间，whos

%s（v0）=true;
%dist=a（v0:）;
path（v0）=v0;dist（v0）=0;
for i = 1:n
    %m = min（dist（~s））;%找到s集之外的点到v0距离的最小值m
    %v = find（dist==m1）;%找到对应m的点
    m = inf;
    for w = 1:n
        if （~s（w） && （dist（w） < m））
            v = w;
            m = dist（w）;
        end
    end
    s（v） = true;
    for w=1:n
        if（~s（w） && m+a（vw） < dist（w））
            dist（w） = m+a（vw）;
            path（w）=v;
        end
    end
end
dist
%path
disp（‘path:‘）;
for i = 1:n
    if i ~= v0
        fprintf（1‘%d to %d :‘v0 i）;
        print_path（v0ipath）;
        disp（‘ ‘）;
    end
end

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

     文件        259  2011-07-22 15:43  print_path.m

     文件       1372  2011-07-22 22:12  Dijkstra2.m

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

                 1631                    2