matlab 五环最小路径算法

function [dist, path] = dijkstra(graph, source, dest)
% graph: n * n 的矩阵，代表无向图
% source：指定的起点
% dest：指定的终点
% dist：起点到各个点的最短距离
% path：起点到终点的最短路径

n = size(graph, 1);
S = false(1, n);
dist = inf(1, n);
prev = zeros(1, n);

dist(source) = 0;

while sum(~S) > 0
    u = find(dist == min(dist(~S)), 1);
    if u == dest
        break;
    end
    S(u) = true;

    for v = 1:n
        if graph(u, v) > 0 && ~S(v)
            new_dist = dist(u) + graph(u, v);
            if new_dist < dist(v)
                dist(v) = new_dist;
                prev(v) = u;
            end
        end
    end
end

path = [];
u = dest;
while prev(u) ~= 0
    path = [u, path];
    u = prev(u);
end
path = [source, path, dest];

end