最短路算法框架

最短路有五种算法，分别适用不同的情况。

单源最短路： 求一个点到其他点的最短路
多源最短路： 求任意两个点的最短路

稠密图用邻接矩阵存，稀疏图用邻接表存储。

稠密图： m 和 n2 一个级别
稀疏图： m 和 n 一个级别

参考：最短路算法总结（超详细~）_wmy0217_的博客-CSDN博客_最短路算法

Dijkstra算法的程序如下：

function [d, p] = dijkstra(adj, s, t)
% 使用dijkstra求最短路径
% adj       输入  矩阵          邻接矩阵
% s         输入  整数          起点
% t         输入  整数 或 []    终点
% d         输出  向量          路径长度，若t==[]，则返回从起点到所有节点的路径长度
% p         输出  向量 或 元胞   路径，若t==[]，则返回从起点到所有节点的路径(cell)
nodes_num = size(adj, 1);
dist = inf(nodes_num, 1);
previous = inf(nodes_num, 1);
Q = [1:nodes_num]';
 
% 求邻居
neighbors = cell(nodes_num, 1);
for i = 1:nodes_num; neighbors{i} = find(adj(i, :) > 0); end
 
dist(s) = 0;
while ~isempty(Q)
    % 取出距离最小点
    [~, min_ind] = min(dist(Q));
    min_node = Q(min_ind);
    Q = setdiff(Q, min_node);
 
    % 若是终点，则结束程序
    if min_node == t
        d = dist(min_node);
        p = generate_path(previous, t);
        return;
    end
 
    % 更新邻居的距离
    for i = 1:length(neighbors{min_node})
        neighbor = neighbors{min_node}(i);
        alt = dist(min_node) + adj(min_node, neighbor);
        if alt < dist(neighbor)
            dist(neighbor) = alt;
            previous(neighbor) = min_node;
        end
    end 
end
d = dist;
p = cell(nodes_num, 1);
for i = 1:nodes_num; p{i} = generate_path(previous, i); end
end
 
% 由前趋推出路径
function path = generate_path(previous, t)
path = [t];
while previous(t) <= length(previous)
    path = [previous(t) path];
    t = previous(t);
end
end

先在编辑器中输入以上代码。

找下图中顶点间最短距离

在这样一张图中，找到从A到D的最短距离和路径。构造邻接矩阵如下：（在命令行窗口输入）

adj = [
    0 12 0 0 0 16 14;
    12 0 10 0 0 7 0;
    0 10 0 3 5 6 0;
    0 0 3 0 4 0 0;
    0 0 5 4 0 2 8;
    16 7 6 0 2 0 9;
14 0 0 0 8 9 0];

 

 

第一行代表A，第二行B……

指定起点和终点：（命令行窗口输入，结果显示在工作区）

[dist, path] = dijkstra(adj, 1, 4);

结果如下：

 

 

Adj是矩阵，即图形；dist是由A到D点的最短距离；path是1~6~5~4，因为矩阵中第一行是A，第二行是B……第七行是G。所以为A~F~E~G。

参考：

dijkstra算法matlab程序_Dijkstra算法例子_张口袋的博客-CSDN博客