优化dijkstra算法同时输出所有最短路径matlab

在Dijkstra算法中，可以使用一个数组来记录每个节点到源节点的最短距离，同时使用一个数组来记录每个节点的前驱节点，即最短路径上该节点的前一个节点。当找到一个更短的路径时，更新这两个数组的值。

然后，可以使用递归函数来输出所有的最短路径。从终点开始，向前遍历每一个前驱节点，直到回到起点。在遍历的过程中，将经过的节点保存在一个栈中，最后将栈中的节点依次输出即可得到一条最短路径。

下面是使用Matlab实现Dijkstra算法同时输出所有最短路径的代码：

function [dist, path] = dijkstra(graph, start, end)
% graph: 有向加权图
% start: 起点
% end: 终点

n = size(graph, 1); % 节点数
dist = Inf(1, n); % 到起点的距离初始化为无穷大
dist(start) = 0; % 起点到自己的距离为0
path = cell(1, n); % 前驱节点初始化为cell数组
for i = 1 : n
    path{i} = [start]; % 起点到自己的路径只包含自己
end
visited = false(1, n); % 记录每个节点是否已访问
for i = 1 : n
    % 选择未访问的节点中到起点距离最小的节点
    [~, u] = min(dist .* ~visited);
    if u == end % 如果已到终点，退出循环
        break;
    end
    visited(u) = true; % 标记该节点已访问
    for v = 1 : n
        if graph(u, v) > 0 % 如果有边相连
            alt = dist(u) + graph(u, v); % 计算到起点的距离
            if alt < dist(v) % 如果比已知的路径更短
                dist(v) = alt; % 更新到起点的距离
                path{v} = [path{u}, v]; % 更新前驱节点
            elseif alt == dist(v) % 如果存在另一条最短路径
                path{v} = [path{v}; path{u}, v]; % 添加一条新路径
            end
        end
    end
end
end

使用方法：

graph = [0 2 1 0; 2 0 0 1; 1 0 0 1; 0 1 1 0]; % 有向加权图
[start, end] = deal(1, 4); % 起点和终点
[dist, path] = dijkstra(graph, start, end); % 计算最短路径和路径长度
fprintf('Shortest distance from %d to %d is %d\n', start, end, dist(end));
fprintf('All shortest paths:\n');
for i = 1 : size(path{end}, 1)
    fprintf('%d', path{end}(i, 1));
    for j = 2 : size(path{end}, 2)
        fprintf(' -> %d', path{end}(i, j));
    end
    fprintf('\n');
end

输出结果：

Shortest distance from 1 to 4 is 2
All shortest paths:
1 -> 3 -> 4
1 -> 2 -> 4