D算法

大家好，我是讯享网，很高兴认识大家。

1 概述

D算法，即Dijkstra算法，它的作用是找出某个节点到其它节点的最短距离。本文使用MATLAB实现D算法，使整个算法非常简洁。从之前的学习中知道，MATLAB实现矩阵操作是非常高效的，所以本文尽量使用了矩阵操作来替代循环操作。这种做法一方面是提高了程序的效率，另一方面能够使程序更加简洁。但是这种做法在某些情况下也不见得是优点。首先，将一个循环程序转换为矩阵操作需要一定的时间，并且有时候比较难。其次，MATLAB的作用相当于“急先锋”，快速实现人们的想法，但是最后应用的，往往是使用C/C++。这样就会出现一些问题，这里描述两个我所遇到和想到的问题。问题一，有的时候在MATLAB中非常高效的程序转换为C/C++之后反而变慢了。这个问题来源于我之前参与的一个项目，项目中使用了聚类算法K-means。利用MATLAB中集成的函数，该聚类算法执行速度很快，但是移植到C/C++上之后却慢了很多。原因就是MATLAB中的矩阵操作其实是很高效的。问题二，大量集成的函数会增加移植的难度。这个问题是显而易见的，MATLAB能得到广泛使用与它集成的很多快捷的函数是离不开的，但是在移植的过程中这些函数可能需要自己重写，这就增加了移植的难度。

2 算法框架

D算法的算法框架如图1所示。

讯享网

图1 D算法实现框架

3 程序代码

3.1 源代码

% D算法实现 % 备注：本程序使用所有直连路径长度的和+1作为无穷大长度 clear all; close all; InData = textread('例2_3_2.txt'); Infinite = sum(sum(InData.*double((InData>=0))))/2+1;  %计算所有直接相连的路径长度+1，作为无穷大 InData = InData.*(double(InData<0).*(-1).*(Infinite))+InData.*(double(InData>=0)); Gp = uint32(zeros(1,size(InData,1)));  %保存顶点 Gpp = ones(1,size(InData,1))*Infinite;  %保存顶点相应权重 Gr = 1:size(InData,1);  %G-Gp Grr = InData(1,:);  %与G-Gp所对应的权重 for ii = 1:size(InData,1)     [TempMin,index] = min(Grr);     Gp(ii) = Gr(index);     Gpp(ii) = TempMin;         % 更新，这是最关键的部分，本质上也简单，就是将每个新加入的点最为中间点，     % 看是否会产生更近的路径。     Gr(index) = [];     temp = Gpp(ii)+InData(Gp(ii),:);     temp = InData(1,:)-temp;     temp = temp.*double((temp>0));     temp = sum(temp,1);     InData(1,:) = InData(1,:)-temp;     Grr = InData(1,:);     Grr(Gp(1:ii)) = []; end

讯享网

3.2 代码分析

本文的正无穷也是设定的一个相对值。同时本文的代码中大量使用了矩阵运算来是程序变得精简，为了说明本文所示代码的精简程度，3.3贴出网上的一个D算法实现版本，同样是使用MATLAB。同时需要说明一点，就是为什么我会使用ii来控制循环。因为在MATLAB中，i和j又可以用来表示虚数，所以一般不会像C/C++一样用来控制循环。

3.3 一个网上寻找的D算法实现代码

讯享网function [ distance path] = Dijk( W,st,e )  %DIJK Summary of this function goes here  %   W  权值矩阵   st 搜索的起点   e 搜索的终点  n=length(W);%节点数  D = W(st,:);  visit= ones(1:n); visit(st)=0;  parent = zeros(1,n);%记录每个节点的上一个节点    path =[];    for i=1:n-1      temp = [];      %从起点出发，找最短距离的下一个点，每次不会重复原来的轨迹，设置visit判断节点是否访问      for j=1:n         if visit(j)             temp =[temp D(j)];         else             temp =[temp inf];         end               end            [value,index] = min(temp);           visit(index) = 0;            %更新 如果经过index节点，从起点到每个节点的路径长度更小，则更新，记录前趋节点，方便后面回溯循迹      for k=1:n          if D(k)>D(index)+W(index,k)             D(k) = D(index)+W(index,k);             parent(k) = index;          end      end             end    distance = D(e);%最短距离  %回溯法  从尾部往前寻找搜索路径  t = e;  while t~=st && t>0   path =[t,path];    p=parent(t);t=p;  end  path =[st,path];%最短路径 end

4 实验结果

4.1 输入数据说明

为了便于MATLAB读取数据方便，原始数据中使用-1来表示正无穷。图2展示了输入的数据。

图2 输入数据

4.2 实验结果说明

程序的运行结果如图3所示。其中Gp中保存了目的节点，Gpp中保存了需要经过的路径长度。

图3 程序运行结果

对比图3和图4可知程序运行结果正确。

图4