Dijkstra算法matlab实现并计算最短路径值

好的，我可以帮你实现Dijkstra算法的Matlab代码，并计算最短路径值。

Dijkstra算法是一种用于解决带权重有向图或者无向图的单源最短路径问题的贪心算法。下面是Dijkstra算法的Matlab实现代码，注释中包含了详细的解释：

function [dist, path] = dijkstra_algorithm(graph, source_node)
% graph: 一个n*n的矩阵，表示有向图或无向图的邻接矩阵
% source_node: 源节点
% dist: 从源节点到其他所有节点的最短距离
% path: 从源节点到其他所有节点的最短路径

n = length(graph); % 获取图中节点的个数
dist = Inf(1, n); % 初始化所有节点到源节点的距离为无穷大
visited = false(1, n); % 初始化所有节点的访问状态为未访问
prev = zeros(1, n); % 记录最短路径中每个节点的前一个节点

dist(source_node) = 0; % 源节点到自己的距离为0

for i = 1:n
    min_dist = Inf;
    u = -1;
    % 找到当前未访问节点中距离源节点最近的节点
    for j = 1:n
        if ~visited(j) && dist(j) < min_dist
            u = j;
            min_dist = dist(j);
        end
    end
    if u == -1 % 当前没有未访问的节点，退出循环
        break
    end
    visited(u) = true; % 将最近的节点标记为已访问
    % 更新与最近节点相邻的未访问节点的距离
    for v = 1:n
        if ~visited(v) && graph(u, v) ~= Inf && dist(u) + graph(u, v) < dist(v)
            dist(v) = dist(u) + graph(u, v);
            prev(v) = u;
        end
    end
end

path = cell(1, n); % 初始化路径
for i = 1:n
    if i == source_node % 源节点到自己的路径为自己
        path{i} = num2str(i);
    elseif prev(i) == 0 % 源节点到该节点没有路径
        path{i} = 'No path exists';
    else % 从源节点到该节点的路径
        path{i} = num2str(i);
        j = i;
        while j ~= source_node
            j = prev(j);
            path{i} = [num2str(j) ' -> ' path{i}];
        end
        path{i} = [num2str(source_node) ' -> ' path{i}];
    end
end

现在我们可以使用上面的代码来计算最短路径。假设我们有以下的邻接矩阵：

graph = [0, 7, Inf, 5;
         7, 0, 8, 9;
         Inf, 8, 0, Inf;
         5, 9, Inf, 0];

源节点是1，我们可以调用dijkstra_algorithm函数来计算最短路径：

[source_dist, source_path] = dijkstra_algorithm(graph, 1);

这将返回源节点到每个节点的最短距离和最短路径。