dijkstra算法求一个最短路问题

Dijkstra算法是一种用于解决带权重图中的单源最短路径问题的算法，其中权重可以是负数，但不能存在负权重的环。该算法在使用中需要构建一个最短路径树，同时记录每个顶点到源节点的最短距离。

以下是Dijkstra算法的具体步骤：
1. 创建一个空的最短路径树，并将源节点添加进去。同时初始化每个节点的距离值为无穷大，源节点距离为0。
2. 遍历与源节点相连的所有节点，更新这些节点的距离值为与源节点相连边的权重值，并将这些节点添加到最短路径树中。
3. 从未加入最短路径树的节点中选择距离值最小的节点，并将其加入到最短路径树中。
4. 更新新加入节点相连的所有节点的距离值，如果更新后的距离值比原来的小，则更新它们的距离值。
5. 重复执行步骤3和步骤4，直到所有节点都加入到最短路径树中，或者找到了目标节点。

以下是Matlab代码实现Dijkstra算法，其中graph表示输入的邻接矩阵，start_node表示起始节点编号，end_node表示目标节点编号：

function [dist,path] = dijkstra(graph, start_node, end_node)
% 初始化dist和path
num_nodes = size(graph, 1);
dist = inf(num_nodes, 1);
path = zeros(num_nodes, 1);
visited = zeros(num_nodes, 1);

dist(start_node) = 0;
path(start_node) = -1;

% 迭代计算最短路径
for i=1:num_nodes
    % 选择未访问节点中距离最小的节点
    min_dist = inf;
    min_index = -1;
    for j=1:num_nodes
        if ~visited(j) && dist(j) < min_dist
            min_dist = dist(j);
            min_index = j;
        end
    end
    
    % 如果找不到可达节点，则退出
    if min_index == -1
        break;
    end
    
    % 更新dist和path
    visited(min_index) = 1;
    for j=1:num_nodes
        if graph(min_index,j) > 0 && ~visited(j)
            new_dist = dist(min_index) + graph(min_index,j);
            if new_dist < dist(j)
                dist(j) = new_dist;
                path(j) = min_index;
            end
        end
    end
    
    % 如果已经找到目标节点，则退出
    if min_index == end_node
        break;
    end
end

% 构建最短路径
if path(end_node) == 0
    path = [];
else
    path_nodes = [];
    current_node = end_node;
    while current_node ~= -1
        path_nodes = [path_nodes; current_node];
        current_node = path(current_node);
    end
    path = flip(path_nodes)';
end
end