dijkstra算法matlab源代码

以下是Dijkstra算法在MATLAB中的源代码：

function [dist, path] = dijkstra(adjMat, startNode, endNode)
% DIJKSTRA Find shortest path from startNode to endNode in a weighted graph
%   [dist, path] = DIJKSTRA(adjMat, startNode, endNode) returns the shortest
%   distance (dist) and path (path) between startNode and endNode in a weighted
%   graph represented by the adjacency matrix adjMat.
%
%   Example:
%       adjMat = [0 5 2 0 0 0;
%                 5 0 0 7 0 0;
%                 2 0 0 1 4 0;
%                 0 7 1 0 6 3;
%                 0 0 4 6 0 8;
%                 0 0 0 3 8 0];
%       [dist, path] = dijkstra(adjMat, 1, 6);
%
%   Written by David Young, updated on March 28, 2021

% Get number of nodes in graph
numNodes = size(adjMat, 1);

% Initialize distances to infinity and previous nodes to zero
dist = inf(1, numNodes);
prev = zeros(1, numNodes);

% Set distance of starting node to zero
dist(startNode) = 0;

% Create array of unvisited nodes
unvisited = 1:numNodes;

while ~isempty(unvisited)
    % Find node with smallest distance
    [~, minNodeIdx] = min(dist(unvisited));
    minNode = unvisited(minNodeIdx);
    
    % If the minimum distance node is the end node, we're done
    if minNode == endNode
        break;
    end
    
    % Update distances to neighbors of minimum distance node
    for neighbor = find(adjMat(minNode, :))
        if ismember(neighbor, unvisited)
            altDist = dist(minNode) + adjMat(minNode, neighbor);
            if altDist < dist(neighbor)
                dist(neighbor) = altDist;
                prev(neighbor) = minNode;
            end
        end
    end
    
    % Remove minimum distance node from unvisited list
    unvisited(minNodeIdx) = [];
end

% Construct path from start node to end node
path = endNode;
while path(1) ~= startNode
    path = [prev(path(1)), path];
end

end

该函数的输入参数为邻接矩阵adjMat、起始节点startNode和目标节点endNode。函数的输出为最短距离dist和最短路径path。

该算法的时间复杂度为O(N^2)，其中N表示图中节点的数量。如果使用堆或优先队列数据结构来存储未访问节点，并对其进行更新，可以将时间复杂度降至O(MlogN)，其中M表示图中边的数量。