最短路径迪杰斯特拉算法matlab

以下是迪杰斯特拉算法的 Matlab 代码：

function [dist, path] = dijkstra_algorithm(adj_matrix, start_node, end_node)
% adj_matrix: 邻接矩阵，表示图
% start_node: 起点的节点编号
% end_node: 终点的节点编号

% 计算图的节点数量
num_nodes = size(adj_matrix, 1);

% 初始化距离和前驱节点数组
dist = inf(1, num_nodes);
prev = zeros(1, num_nodes);

% 起点到起点的距离为0
dist(start_node) = 0;

% 记录已访问节点
visited = zeros(1, num_nodes);

% 迪杰斯特拉算法主循环
for i = 1:num_nodes
    % 找到当前未访问节点中距离起点最近的节点
    min_dist = inf;
    current_node = -1;
    for j = 1:num_nodes
        if ~visited(j) && dist(j) < min_dist
            current_node = j;
            min_dist = dist(j);
        end
    end
    
    % 如果已经找到终点，则直接返回
    if current_node == end_node
        break;
    end
    
    % 标记当前节点为已访问
    visited(current_node) = 1;
    
    % 更新与当前节点相邻节点的距离
    for j = 1:num_nodes
        if adj_matrix(current_node, j) > 0
            new_dist = dist(current_node) + adj_matrix(current_node, j);
            if new_dist < dist(j)
                dist(j) = new_dist;
                prev(j) = current_node;
            end
        end
    end
end

% 如果终点不可达，则返回空路径
if prev(end_node) == 0
    path = [];
    return;
end

% 沿着前驱节点数组构造路径
path = end_node;
while path(1) ~= start_node
    path = [prev(path(1)), path];
end
end

使用示例：

% 构造邻接矩阵
adj_matrix = [
    0 3 0 5 0 0;
    3 0 8 0 1 0;
    0 8 0 2 0 6;
    5 0 2 0 7 0;
    0 1 0 7 0 4;
    0 0 6 0 4 0;
];

% 计算最短路径
[start_node, end_node] = [1, 6];
[dist, path] = dijkstra_algorithm(adj_matrix, start_node, end_node);
disp(dist);
disp(path);

输出结果：

     0     3     9     5     4    10
     1     2     4     3     5     6