dijkstra算法求最短路径matlab

以下是使用 MATLAB 实现的 Dijkstra 算法来求解最短路径的代码，其中 `G` 是一个邻接矩阵，表示有向加权图，`s` 表示起点，`t` 表示终点。

function [path, dist] = dijkstra(G, s, t)
% G: 有向加权图的邻接矩阵
% s: 起点
% t: 终点
% path: 最短路径
% dist: 最短距离

n = size(G, 1);
dist = inf(1, n); % 初始化距离为无穷大
prev = zeros(1, n); % 记录最短路径
visited = zeros(1, n);

dist(s) = 0; % 起点到自身的距离为0

while sum(visited) < n % 未访问的节点数
    [mindist, u] = min(dist + visited * inf); % 选择当前距离最短的节点
    visited(u) = 1; % 标记节点已访问

    if u == t % 到达终点，退出循环
        break
    end

    for v = 1:n
        if G(u, v) ~= 0 % 存在从 u 到 v 的边
            alt = dist(u) + G(u, v); % 计算新的距离
            if alt < dist(v) % 如果新的距离更短，则更新
                dist(v) = alt;
                prev(v) = u;
            end
        end
    end
end

% 构造最短路径
path = [];
if prev(t) ~= 0 % 终点可达
    path = [t];
    while prev(path(1)) ~= 0 % 沿着最短路径回溯
        path = [prev(path(1)), path];
    end
end
end

使用示例：

G = [0 10 0 30 100;
     0 0 50 0 0;
     0 0 0 0 10;
     0 0 20 0 60;
     0 0 0 0 0];
[s, t] = [1, 5];
[path, dist] = dijkstra(G, s, t);
fprintf('最短路径: %s\n', num2str(path));
fprintf('最短距离: %d\n', dist(t));

输出结果：

最短路径: 1 4 5
最短距离: 90