求两点间最短路的Dijkstra算法及其matlab程序详解

#################本文为学习《图论算法及其MATLAB实现》的学习笔记#################

设源点为 u 0 u_{0} u0​,目标点为 v 0 v_{0} v0​。

Dijkstra算法的基本思想

按距离 u 0 u_{0} u0​ 由近及远为顺序，依次求得 u 0 u_{0} u0​ 到 G 的各顶点的最短路和距离，直至 v 0 v_{0} v0​ (或直至 G 的所有顶点)，算法结束。

为避免重复并保留每一步的计算信息，采用了标号算法。

Dijkstra算法

程序参数说明

A: 图的权值矩阵
d: 所求最短路的权和
index1: 标号顶点顺序
index2: 标号顶点索引

算法的matlab程序详解

function [ d ,index1 ,index2 ] = Dijkf( A )
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%% 两点间最短路的Dijkstra算法 %%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%% 输入：     A: 图的权值矩阵 
%%%%%%%%% 输出：     d: 所求最短路的权和
%%%%%%%%%       index1: 标号顶点顺序
%%%%%%%%%       index2: 标号顶点索引
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%% 参数初始化 %%%%%%%%%%%%
M = max(max(A));        % 返回 A 中最大值，即图中权值最大的边
pb(1:length(A)) = 0;    % pb 为维度为 a 顶点数的全零数组
pb(1) = 1;
index1 = 1;
index2 = ones(1,length(A));     % index2 为维度为图顶点数的全1数组
d(1:length(A)) = M;     % d 为维度为图顶点数，值全为最大边权值的数组
d(1) = 0;
temp = 1;

%%%%%%%%%%% 更新l（v)同时记录顶点索引和顺序 %%%%%%%%%%%
% 重复步骤2，直到满足条件
while sum(pb) < length(A)       % 检验 pb 元素和(即已标号顶点数)是否小于顶点数
    tb = find(pb == 0);         % tb 为 pb 中零元素的索引值，即未标号的顶点
    d(tb) = min(d(tb),d(temp) + A(temp,tb));    % 更新l(v),即与当前顶点相邻的顶点的标号{标号取（当前顶点标号值与相邻顶点之间的边权值的和，相邻顶点标号值)的最小值}
    tmpb = find(d(tb) == min(d(tb)));           % 返回与当前顶点最近的顶点在 tb 中的索引值
    temp = tb(tmpb(1));         % 返回与当前顶点最近的顶点(未访问过)
    pb(temp) = 1;               % 将新的顶点写入访问队列
    index1 = [index1,temp];     % 将新顶点写入最短路路径中，即记录标号顺序
    index = index1(find(d(index1) == d(temp) - A(temp,index1)));
    if length(index) >= 2       % 判断 index 元素个数是否大于2
        index = index(1);
    end
    index2(temp) = index;       % 记录标号索引
end

d;
index1;
index2;