用matlab实现dijkstra算法求最短路径

Dijkstra算法是一种用于计算加权图的最短路径的算法。下面是用MATLAB实现Dijkstra算法的示例代码。

function [dist, path] = dijkstra(graph, start, dest)
%DIJKSTRA Calculates the shortest path in a graph using Dijkstra's algorithm
%   [DIST, PATH] = DIJKSTRA(GRAPH, START, DEST) calculates the shortest path
%   in the graph GRAPH from node START to node DEST using Dijkstra's algorithm.
%   DIST is the distance of the shortest path and PATH is a vector of node
%   indices representing the path from START to DEST.
%
%   GRAPH is an N x N matrix representing the adjacency matrix of the graph
%   where N is the number of nodes in the graph. The element GRAPH(i,j) is the
%   weight of the edge from node i to node j. If there is no edge from node i
%   to node j, then GRAPH(i,j) should be set to Inf.
%
%   START and DEST are scalar values representing the starting and ending nodes
%   of the path to be found.

% Initialize the distance vector and the visited set
dist = Inf(size(graph, 1), 1);
visited = false(size(graph, 1), 1);

% Set the distance to the starting node to 0
dist(start) = 0;

% Loop until the destination node is visited
while ~visited(dest)
    % Find the node with the minimum distance
    [~, idx] = min(dist(~visited));
    if isempty(idx)
        error('No path exists from start to destination');
    end
    curr = find(~visited, idx(1), 'first');

    % Update the distances to the neighbors of the current node
    neighbors = find(graph(curr, :) ~= Inf);
    for i = 1:length(neighbors)
        node = neighbors(i);
        if ~visited(node)
            alt = dist(curr) + graph(curr, node);
            if alt < dist(node)
                dist(node) = alt;
                path(node) = curr;
            end
        end
    end

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

% Reconstruct the path
path = dest;
while path(1) ~= start
    path = [path(1), path];
    path(1) = path(2);
    path(2) = path(3);
end
path = [start, path];
end

这个函数接受一个邻接矩阵作为输入，该矩阵表示图的结构，以及起点和终点。返回值是两个向量，一个是最短距离，另一个是路径。可以使用以下代码来测试函数：

graph = [Inf, 2, 3, Inf, Inf;
         2, Inf, 4, 1, Inf;
         3, 4, Inf, 1, 5;
         Inf, 1, 1, Inf, 2;
         Inf, Inf, 5, 2, Inf];
[start, dest] = deal(1, 5);
[dist, path] = dijkstra(graph, start, dest);
fprintf('Shortest distance from node %d to node %d: %d\n', start, dest, dist(dest));
fprintf('Path from node %d to node %d: %s\n', start, dest, num2str(path));

这段代码将输出从节点1到节点5的最短距离和路径。