最短路算法框架
最短路有五种算法,分别适用不同的情况。
单源最短路: 求一个点到其他点的最短路
多源最短路: 求任意两个点的最短路
稠密图用邻接矩阵存,稀疏图用邻接表存储。
稠密图: 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博客