迪杰斯特拉最短路径完整代码matlab

以下是迪杰斯特拉算法的完整代码，使用Matlab编写：

function [distances, previous] = dijkstra(adjacency_matrix, start_node)
% DIJKSTRA Calculates the shortest path between nodes in a graph using the Dijkstra algorithm
%   [distances, previous] = DIJKSTRA(adjacency_matrix, start_node) returns the distances
%   from the start_node to each node in the graph and the previous node for each node on the
%   shortest path from start_node to that node.
%
%   adjacency_matrix is a square matrix representing the weighted edges of the graph
%   start_node is the index of the starting node
%
%   Example usage:
%
%       >> adjacency_matrix = [0 7 Inf 5; 7 0 8 9; Inf 8 0 Inf; 5 9 Inf 0]
%       >> [distances, previous] = dijkstra(adjacency_matrix, 1)
%       distances =
%            0     7    15     5
%       previous =
%            0     1     2     1

    % Initialize variables
    num_nodes = size(adjacency_matrix, 1);
    visited = false(1, num_nodes);
    distances = Inf(1, num_nodes);
    previous = zeros(1, num_nodes);

    % Set the distance to the start node to 0
    distances(start_node) = 0;

    % Loop through all nodes in the graph
    for i = 1:num_nodes
        % Find the node with the smallest distance that has not been visited yet
        [min_distance, current_node] = min(distances(~visited));

        % If all remaining nodes are inaccessible, break out of the loop
        if isempty(current_node)
            break;
        end

        % Mark the current node as visited
        visited(current_node) = true;

        % Loop through all neighbors of the current node
        for j = 1:num_nodes
            if adjacency_matrix(current_node, j) ~= Inf && ~visited(j)
                % Calculate the distance to the neighbor through the current node
                distance = min_distance + adjacency_matrix(current_node, j);

                % If the distance is shorter than the current shortest distance to the neighbor, update it
                if distance < distances(j)
                    distances(j) = distance;
                    previous(j) = current_node;
                end
            end
        end
    end
end

使用方法：

1. 定义一个邻接矩阵，其中 Inf 表示两个节点之间没有边连接
2. 调用 dijkstra 函数，传递邻接矩阵和起始节点的索引作为参数
3. 函数将返回一个距离数组和前驱节点数组，其中距离数组表示从起始节点到每个节点的最短距离，前驱节点数组表示从起始节点到每个节点的最短路径上每个节点的前一个节点的索引，如果不存在前驱节点，则为0