博文

目前显示的是 十月, 2019的博文

Dijkstra算法详解 - matlab实现

此页面正在编辑完善中,目前仅贴代码。% author: GZH function [min_distance , min_path] = min_distance(matrix, first, last) % matrix -- 输入邻接矩阵 % start -- 起点, end -- 终点 % 输出:min_diatance -- 最短路距离, min_path -- 最短路回溯路径 n = size(matrix, 1); % 矩阵行数 open(1:n) = 0; % 开放队列,0可访问,1不可访问 distance(1:n) = inf; distance(first) = 0; % 各点到起始点的距离矩阵 open(first) = 1; u = first; % u为当前到目标距离最小的点的标号 partent(1:n) = 0; % 回溯队列,对应顶点的前驱节点 for i = 1:n-1 id = find(open == 0); % 查找开放队列中可访问的顶点 for v = id if matrix(u, v) + distance(u) < distance(v) distance(v) = matrix(u, v) + distance(u); % 更新最小距离 partent(v) = u; end end temp = distance; temp(open == 1) = inf; % 已拜访节点值为无穷大,使其不可再被访问 [t, u] = min(temp); % 寻找更新后的最小距离顶点 open(u) = 1; % 最小顶点从开放列表移除 end min_path = []; if partent(last) ~= 0 % 存在通路 t = last; min_path = [last]; while t ~= first p = partent(t); min_path = [p min_path]; t = p; end else fprintf('不存在通路,请重…