迪杰斯特拉算法matlab

以下是Dijkstra算法的Matlab代码实现：

function [dist, path] = Dijkstra(graph, start, dest)
% Dijkstra算法求解单源最短路径
% 输入参数：graph-邻接矩阵，start-起点，dest-终点
% 输出参数：dist-最短距离，path-最短路径

n = size(graph, 1); % 图的大小
dist = Inf(1, n); % 初始化距离
visited = zeros(1, n); % 初始化visited
prev = zeros(1, n); % 初始化prev

dist(start) = 0;

for i = 1:n-1
    min_dist = Inf;
    for j = 1:n
        if ~visited(j) && dist(j)<min_dist
            min_dist = dist(j);
            u = j;
        end
    end
    visited(u) = 1;
    for v = 1:n
        if ~visited(v) && (graph(u, v)~=Inf) && (dist(u)+graph(u, v)<dist(v))
            dist(v) = dist(u) + graph(u, v);
            prev(v) = u;
        end
    end
end

path = [];
if dist(dest)~=Inf
    t = dest;
    while t~=start
        path = [t path];
        t = prev(t);
    end
    path = [start path];
end
end

其中，输入参数graph为邻接矩阵，start和dest分别为起点和终点。输出参数dist为最短距离，path为最短路径。具体实现过程为：

1. 初始化距离dist数组为Inf，visited数组为0，prev数组为0；
2. 将起点start的距离dist[start]赋值为0；
3. for循环n-1次，每次选择未访问节点中dist最小的节点u，将visited[u]设为1；
4. for循环所有节点v，如果v未访问且u到v的距离更短，则更新dist[v]和prev[v]；
5. 循环结束后，如果终点dest的距离dist[dest]不为Inf，则输出最短路径。