最短路径 Dijkstra算法的Matlab代码实现三维

Dijkstra算法是一种用于求解有向图或无向图中最短路径的经典算法。在三维空间中，我们通常需要处理的是三维网格图（Grid Graph），在这种情况下，我们可以稍微修改传统的Dijkstra算法来适应。

以下是使用Matlab实现Dijkstra算法的基本步骤，假设我们有一个稀疏矩阵`adjMatrix`表示三维网格图的邻接关系，其中非零元素表示两个节点间存在边，值为边的权重：

% 初始化
[D, n] = size(adjMatrix);
dist = Inf(1, n); % 初始距离矩阵，所有节点设为无穷大
visited = false(1, n); % 标记已访问的节点
prev = zeros(1, n); % 存储最短路径的前驱节点

% 父节点初始化为自身
parent = ones(1, n) * -1;

% 起始节点的距离设为0
dist(1) = 0;

while ~all(visited) % 当所有节点都访问过时跳出循环
    % 找到未访问的最近节点
    [~, u] = min(dist(~visited)); 
    visited(u) = true; % 标记该节点为已访问
    
    % 更新其相邻节点的距离
    for v = find(adjMatrix(u, :)) % 遍历u的所有邻居
        if ~visited(v) && dist(u) + adjMatrix(u, v) < dist(v)
            dist(v) = dist(u) + adjMatrix(u, v); % 新的距离
            prev(v) = u; % 更新前驱节点
        end
    end
end

% 打印结果
shortest_path = [];
current_node = n;
while current_node ~= -1 % 反向追踪找到最短路径
    shortest_path = [current_node, shortest_path];
    current_node = prev(current_node);
end
shortest_path = shortest_path(end:-1:1); % 逆序得到路径

%