dijkstra最短路径算法的matlab实现 包括最短路径的打印子程序

在MATLAB中实现Dijkstra最短路径算法包括以下步骤：

1. 初始化：
- 创建一个矩阵 `dist` 用于存储每个节点到起始节点的距离，初始时将所有节点的距离设置为无穷大，除了起始节点的距离设置为0。
- 创建一个矩阵 `visited` 用于标记每个节点是否被访问过，初始时将所有节点的访问状态设置为未访问。
- 创建一个向量 `prev` 用于存储到达每个节点的前一个节点，初始时将所有节点的前一个节点设置为起始节点。

2. 运行Dijkstra算法：
- 在 `dist` 中选择距离起始节点最近且未被访问过的节点作为当前节点。
- 更新当前节点的相邻节点的距离，如果通过当前节点到达相邻节点的距离比原先记录的距离更短，则更新 `dist` 中的距离，并将当前节点作为相邻节点的前一个节点。
- 将当前节点标记为已访问。
- 重复以上步骤，直到所有节点都被访问过。

3. 打印最短路径：
- 根据 `prev` 向量，从终点节点开始，沿着每个节点的前一个节点逆向查找，直到找到起点节点。
- 将遍历的节点按照逆序存储在一个向量中。
- 输出这个向量即为起点到终点的最短路径。

注意：在实现中，需要根据具体情况对节点和边的表示方式进行调整。

以下是一个简单的示例，假设图的邻接矩阵为 `graph`，起始节点为 `start`，终点节点为 `end`：

function shortestPath(graph, start, end)
    numNodes = size(graph, 1);
    dist = inf(1, numNodes);  % 用于存储节点到起始节点的距离
    visited = false(1, numNodes);  % 用于标记节点是否被访问过
    prev = zeros(1, numNodes);  % 用于存储到达节点的前一个节点

    % 初始化起始节点的信息
    dist(start) = 0;

    % 执行Dijkstra算法
    for i = 1:numNodes
        % 在未访问的节点中选择距离起始节点最近的节点
        curr = findMinDist(dist, visited);
        visited(curr) = true;

        % 更新相邻节点的距离
        for j = 1:numNodes
            if graph(curr, j) > 0  % 判断两节点是否相邻
                alt = dist(curr) + graph(curr, j);
                if alt < dist(j)
                    dist(j) = alt;
                    prev(j) = curr;
                end
            end
        end
    end

    % 打印最短路径
    path = end;
    while path ~= start
        path = [prev(path), path];
    end
    fprintf('最短路径为：%s\n', num2str(fliplr(path)));  % 输出逆序的最短路径
end

function minNode = findMinDist(dist, visited)
    minDist = inf;
    minNode = -1;
    for i = 1:length(dist)
        if ~visited(i) && dist(i) < minDist
            minDist = dist(i);
            minNode = i;
        end
    end
end

这是一个基本的Dijkstra最短路径算法的MATLAB实现，并包括了输出最短路径的思路。实际应用中可能需要根据具体问题进行调整和优化。