用迪杰斯特拉算法计算指定起点到其他各点的最短路径matlab代码

以下是用 Matlab 实现的 Dijkstra 算法代码，可以用于计算指定起点到其他各点的最短路径：

function [dist,path] = dijkstra(G,s)
% Dijkstra algorithm to compute the shortest path from a source node to all other nodes in a graph
% Input:
%   G: a weighted adjacency matrix of a graph, G(i,j) is the weight of edge (i,j), and G(i,j)=0 if there is no edge
%   s: the index of the source node
% Output:
%   dist: a vector of the shortest distances from the source node to all other nodes
%   path: a matrix of the shortest paths from the source node to all other nodes
% Written by LIN, Jingyu (linjy02@hotmail.com)
% Last modified on 2021-10-11

n = size(G,1);
dist = inf(1,n); % initialize distances to all nodes as infinity
dist(s) = 0; % distance to the source node is zero
path = zeros(n,n); % initialize path matrix
for i = 1:n
    path(i,i) = i; % the path from a node to itself is itself
end
S = []; % set of visited nodes
Q = 1:n; % set of unvisited nodes
while ~isempty(Q)
    [~,u] = min(dist(Q)); % find the node with the minimum distance in Q
    S = [S Q(u)]; % add the node to the set of visited nodes
    Q(u) = []; % remove the node from the set of unvisited nodes
    for v = find(G(u,:)) % for each neighbor of u
        if ~ismember(v,S) % if v is not visited
            alt = dist(u) + G(u,v); % compute the alternative distance from s to v via u
            if alt < dist(v) % if the alternative distance is smaller than the current distance
                dist(v) = alt; % update the distance to v
                path(:,v) = 0; % clear the old path to v
                path(:,v) = path(:,u); % set the new path to v via u
                path(u,v) = v; % add the last hop to the new path
            end
        end
    end
end
end

其中，G 是一个邻接矩阵，表示有向图或无向图的连接关系和边权值；s 是指定的起点节点的索引。函数会返回一个 dist 向量和一个 path 矩阵，分别表示从起点到其他节点的最短距离和最短路径。