dijktra matlab

### Dijkstra算法在MATLAB中的实现

Dijkstra算法是一种用于计算加权图中最短路径的经典算法。该算法能够有效地找到从起始节点到其他所有节点之间的最短距离。

下面是一个简单的基于优先队列的Dijkstra算法的MATLAB实现：

function [dist, prev] = dijkstra(G, start)
% DIJKSTRA 计算给定有向图G中从start出发到达各顶点的最短路径长度及其前驱结点.
%
% 输入参数:
% G    : 图的邻接矩阵表示形式 (稀疏矩阵), 非零元素代表边权重;
% start: 起始节点索引.

n = size(G, 1); % 获取图中节点数量
visited = false(1, n);
distance = inf(1, n);
prev = zeros(1, n);

distance(start) = 0;

while any(~visited)
    % 找到未访问过的具有最小临时距离值的顶点u作为当前处理对象
    [~, u] = min(distance + visited * Inf);
    
    if isnan(u)
        break; % 如果找不到这样的顶点，则结束循环
    end
    
    visited(u) = true;
    
    neighbors = find(G(:, u)); % 寻找与u相邻的所有顶点v
    
    for v = neighbors'
        alt = distance(u) + G(v, u);
        
        if alt < distance(v)
            distance(v) = alt;
            prev(v) = u;
        end
    end
end

此函数接受两个输入参数：`G`, 表示图形结构的一个稀疏矩阵；以及 `start`, 指明要寻找最短路径的源节点编号。输出变量 `dist` 存储着由起点至各个目标位置间的最短路程，而数组 `prev` 则记录了构建这些路线所需的先前节点信息[^3].

为了更好地理解上述过程并验证其正确性，在实际应用之前可以先创建测试数据集来观察结果是否合理。例如，可以通过定义一个简单网格地图上的障碍物分布情况来进行模拟实验，并调用以上编写的dijkstra() 函数求解最优行走方案.