dijkstra算法求有向图最短路径matlab

以下是使用Dijkstra算法求解有向图最短路径的一段MATLAB代码：

function [D, path] = dijkstra(G, start, dest)
% Dijkstra's algorithm to find the shortest path between start and dest.
% G is a weighted digraph with adjacency matrix A.
% start and dest are start and destination nodes respectively.
% D is the shortest path distance.
% path is a vector that contains the path node IDs.

n = size(G, 1); % number of nodes
dist = inf(1, n); % initialize the distance vector
prev = zeros(1, n); % initialize the previous node vector
visited = zeros(1, n); % initialize the visited vector

dist(start) = 0; % distance from start to start is 0

for i = 1:n
    % find the node with the minimum distance
    [~, u] = min(dist .* ~visited);
    visited(u) = 1;
    if u == dest
        break;
    end
    % update the distances of the neighbors of the current node
    for v = 1:n
        if G(u, v) > 0 % there is an edge from u to v
            alt = dist(u) + G(u, v); % the distance from start to v through u
            if alt < dist(v) % a shorter path to v has been found
                dist(v) = alt;
                prev(v) = u;
            end
        end
    end
end

% construct the path vector by traversing backwards from dest to start
path = dest;
while prev(path(end)) ~= 0
    path = [prev(path(end)), path];
end
if path(1) ~= start % there is no path from start to dest
    D = inf;
    path = [];
else
    D = dist(dest);
end

其中，G是有向图的邻接矩阵，start和dest分别是起点和终点的节点编号。函数返回D和path两个变量，分别表示最短路径的长度和路径上的节点编号。如果不存在从start到dest的路径，则返回inf和空数组。