matlab dijkstra 标号算法

Dijkstra算法是一种常见的单源最短路径算法，可以用于计算从一个源点出发到其它所有节点的最短路径。标号法是Dijkstra算法的一种实现方式，它使用了一个数组来记录每个节点的最短路径长度，同时使用一个标记数组来记录哪些节点已经被处理过了。

以下是基于标号法的Dijkstra算法实现的Matlab代码：

function [dist, path] = dijkstra(graph, start)
% graph: n x n 的邻接矩阵，表示图的连接情况和权重
% start: 起点节点的编号（从1开始）
% dist: 从起点到各个节点的最短距离
% path: 从起点到各个节点的最短路径（以节点编号表示）

n = size(graph, 1);  % 图的节点数
dist = inf(1, n);    % 初始时，所有节点距离起点的距离都是无穷大
path = zeros(1, n);  % 初始化路径为0

visited = zeros(1, n);  % 标记数组，用于记录哪些节点已经被处理过了
dist(start) = 0;  % 起点到自身的距离为0

while sum(visited) < n
    % 找到未处理过的距离起点最近的节点
    [min_dist, min_index] = min(dist .* (1 - visited));
    visited(min_index) = 1;  % 标记该节点已经被处理过了
    
    % 更新与该节点相邻的所有节点的距离
    for i = 1:n
        if graph(min_index, i) > 0 && (dist(i) > min_dist + graph(min_index, i))
            dist(i) = min_dist + graph(min_index, i);
            path(i) = min_index;
        end
    end
end

% 将路径转换成节点编号表示
for i = 1:n
    if i == start
        continue;
    end
    temp_path = [];
    j = i;
    while j ~= start
        temp_path = [j temp_path];
        j = path(j);
    end
    temp_path = [start temp_path];
    path(i) = temp_path;
end
end

这个算法的时间复杂度为 O(n^2)，其中 n 是图的节点数，因为在每次循环中需要遍历整个节点集合来找到未处理过的距离起点最近的节点。如果使用堆优化技术，可以将时间复杂度优化到 O(m log n)，其中 m 是图的边数。