请编写一个初级的可在matlab2021运行的Dijkstra算法

以下是一个简单的Dijkstra算法的Matlab代码：

function [D, P] = dijkstra(adj, start)
    % 初始化
    n = size(adj, 1);
    D = Inf(1, n);
    D(start) = 0;
    P = zeros(1, n);

    % 计算最短路径
    for i = 1:n-1
        [~, u] = min(D);
        for v = 1:n
            if adj(u, v) ~= 0 && D(u) + adj(u, v) < D(v)
                D(v) = D(u) + adj(u, v);
                P(v) = u;
            end
        end
        D(u) = Inf;
    end
end

其中，输入参数`adj`是一个邻接矩阵，表示图中各个节点之间的连通情况和边权重；`start`是起点的编号。函数返回值`D`是起点到各个节点的最短路径长度，`P`是最短路径上各个节点的前驱节点。

该算法的时间复杂度为$O(n^2)$，适用于小规模的图。若需要处理大规模的图，可以使用堆优化的Dijkstra算法，时间复杂度为$O(n\log n)$。

相关问题

请编写一个可在matlab2021运行的Dijkstra算法

好的，以下是一个基于 MATLAB 实现的 Dijkstra 算法：

function [dist, path] = dijkstra(adj_matrix, start_node, end_node)
% DIJKSTRA  Compute the shortest path between two nodes in a graph using Dijkstra algorithm.
%
% Input:
%   - adj_matrix: A n-by-n matrix represents the adjacency matrix of the graph. 
%                 adj_matrix(i, j) = the weight of the edge between node i and node j.
%                 If there is no edge between node i and node j, adj_matrix(i, j) = inf.
%   - start_node: The index of the starting node.
%   - end_node:   The index of the ending node.
%
% Output:
%   - dist: A scalar represents the shortest distance between the start_node and end_node.
%   - path: A vector represents the path from the start_node to the end_node.

n = size(adj_matrix, 1);    % Number of nodes in the graph
visited = false(n, 1);      % Visited flag
dist = inf(n, 1);           % Distance from start_node to each node
prev = zeros(n, 1);         % Previous node in the shortest path
dist(start_node) = 0;       % Distance from start_node to start_node is 0

for i = 1:n
    % Find the node with the smallest distance
    [~, u] = min(dist(~visited));
    if isempty(u)
        break;
    end
    visited(u) = true;
    if u == end_node
        break;
    end
    
    % Update the distance of the neighboring nodes
    for v = 1:n
        if ~visited(v) && adj_matrix(u, v) < inf
            alt = dist(u) + adj_matrix(u, v);
            if alt < dist(v)
                dist(v) = alt;
                prev(v) = u;
            end
        end
    end
end

% Compute the path from start_node to end_node
path = [];
u = end_node;
while prev(u) ~= 0
    path = [u, path];
    u = prev(u);
end
if ~isempty(path)
    path = [start_node, path];
end

end

使用方法：

假设我们有一个 5 个节点的图，其邻接矩阵为：

0   4   1   ∞   ∞
4   0   3   2   ∞
1   3   0   4   2
∞   2   4   0   3
∞   ∞   2   3   0

我们想要计算从节点 1 到节点 5 的最短路径，可以使用以下代码：

adj_matrix = [0   4   1   inf inf;
              4   0   3   2   inf;
              1   3   0   4   2;
              inf 2   4   0   3;
              inf inf 2   3   0];
[start_node, end_node] = deal(1, 5);
[dist, path] = dijkstra(adj_matrix, start_node, end_node);

其中 `dist` 是从起点到每个节点的最短距离，`path` 是从起点到终点的最短路径。

请编写一个可运行的Dijkstra算法

以下是一个使用Python编写的Dijkstra算法实现：

import heapq

def dijkstra(adj_matrix, start):
    """
    adj_matrix: 二维数组，表示带权有向图的邻接矩阵
    start: 起点
    """
    n = len(adj_matrix)
    dist = [float('inf')] * n  # 距离初始化为无穷大
    visited = [False] * n  # 标记是否访问过
    dist[start] = 0  # 起点距离为0
    heap = [(0, start)]  # 堆初始化，存储(距离, 节点)二元组
    while heap:
        (d, u) = heapq.heappop(heap)  # 取出堆顶元素
        if visited[u]:  # 如果该节点已访问过，直接跳过
            continue
        visited[u] = True  # 标记为已访问
        for v in range(n):
            if adj_matrix[u][v] > 0:  # 如果该节点有出边
                if dist[v] > dist[u] + adj_matrix[u][v]:  # 如果通过u到v的距离更小
                    dist[v] = dist[u] + adj_matrix[u][v]  # 更新距离
                    heapq.heappush(heap, (dist[v], v))  # 加入堆中
    return dist

使用示例：

# 定义邻接矩阵
adj_matrix = [
    [0, 10, 0, 30, 100],
    [0, 0, 50, 0, 0],
    [0, 0, 0, 0, 10],
    [0, 0, 20, 0, 60],
    [0, 0, 0, 0, 0]
]

# 调用dijkstra函数，计算起点0到其他节点的最短距离
dist = dijkstra(adj_matrix, 0)

# 输出结果
print(dist)  # [0, 10, 50, 30, 60]

这个算法实现了Dijkstra算法的核心思想，即从起点开始，每次选择距离最小的节点进行扩展。具体地，算法使用一个堆来维护所有已经访问过但还未确定最短距离的节点，每次从堆中取出距离最小的节点进行扩展，并更新其邻居节点的距离。最后，算法返回起点到所有节点的最短距离。