1 算法特点

Dijkstra使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题，算法最终得到一个最短路径树。

2 算法的思路

Dijkstra算法采用的是一种贪心的策略，声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合：T。

初始时，原点s的路径权重被赋为0（dis[s]=0）。若对于顶点s存在能直接到达的边（s，m），则把dis[m]设为w（s，m），同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大。初始时，集合T只有顶点s。

然后，从dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点加入到T中，OK，此时完成一个顶点。

然后，需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在dis中的值。

然后，又从dis中找出最小值，重复上述动作，直到T中包含了图的所有顶点。

3 Dijkstra算法示例演示

求从顶点v1到其他各个顶点的最短路径。

图1

首先声明一个dis数组，该数组初始化的值为：

图2

T初始化为：T={v1}。

既然是求v1顶点到其余各个顶点的最短路程，那就先找一个离1号顶点最近的顶点。

通过数组dis可知当前离v1顶点最近是v3顶点。当选择了2号顶点后，dis[2]（下标从0开始）的值就已经从“估计值”变为了“确定值”，即v1顶点到v3顶点的最短路程就是当前dis[2]值。

将v3加入到T中。因为目前离v1顶点最近的是v3顶点，并且这个图所有的边都是正数，那么肯定不可能通过第三个顶点中转，使得v1顶点到v3顶点的路程进一步缩短了。因为v1顶点到其它顶点的路程肯定没有v1到v3顶点短。

既然确定了一个顶点的最短路径，下面我们就要根据这个新入的顶点v3会有出度，发现以v3为弧尾的有：<v3，v4>，那么我们看看路径：v1–>v3–>v4的长度是否比v1–>v4短，其实这个已经是很明显的了，因为dis[3]代表的就是v1–>v4的长度为无穷大，而v1–>v3–>v4的长度为：10+50=60，所以更新dis[3]的值，得到如下结果：

图3

因此dis[3]要更新为60。这个过程有个专业术语叫做“松弛”。即v1顶点到v4顶点的路程即dis[3]，通过<v3，v4>这条边松弛成功。

这便是Dijkstra算法的主要思想：通过“边”来松弛v1顶点到其余各个顶点的路程。

然后，我们又从除dis[2]和dis[0]外的其他值中寻找最小值，发现dis[4]的值最小，通过之前是解释的原理，可以知道v1到v5的最短距离就是dis[4]的值，然后，我们把v5加入到集合T中，然后，考虑v5的出度是否会影响我们的数组dis的值，v5有两条出度：<v5，v4>和<v5，v6>，然后我们发现：v1–>v5–>v4的长度为：50，而dis[3]的值为60，所以我们要更新dis[3]的值。另外，v1–>v5–>v6的长度为：90，而dis[5]为100，所以我们需要更新dis[5]的值。更新后的dis数组如下图：

图4

然后，继续从dis中选择未确定的顶点的值中选择一个最小的值，发现dis[3]的值是最小的，所以把v4加入到集合T中，此时集合T={v1,v3,v5,v4},然后，考虑v4的出度是否会影响我们的数组dis的值，v4有一条出度：<v4，v6>,然后我们发现：v1–>v5–>v4–>v6的长度为：60，而dis[5]的值为90，所以我们要更新dis[5]的值，更新后的dis数组如下图：

图5

然后，我们使用同样原理，分别确定了v6和v2的最短路径，最后dis的数组的值如下：

图6

因此，从图中，我们可以发现v1–>v2的值为：∞，代表没有路径从v1到达v2。所以我们得到的最后的结果为：

表1

4 Dijkstra的时间复杂度

用大O符号将Dijkstra算法的运行时间表示为边数m和顶点数n的函数。

Dijkstra算法最简单的实现方法是用一个链表或者数组来存储所有顶点的集合Q，所以搜索Q中最小元素的运算只需要线性搜索Q中的所有元素。这样的话算法的运行时间是

 [公式] 。

对于边数少于 n^2 稀疏图来说，我们可以用邻接表来更有效的实现Dijkstra算法。

同时需要将一个二叉堆或者斐波纳契堆用作优先队列来寻找最小的顶点。

当用到二叉堆的时候，算法所需的时间为 O((m+n)logn)，斐波纳契堆能稍微提高一些性能，让算法运行时间达到O(m+nlogn)。

5 例子

让我们再通过一个例子了解Dijkstra的原理。

图7

图8

图9

图10

图11

图12

6 代码

clc;
clear;
close all;
%% load obs
obs = load('obsdata.txt');
numofobs = length(obs(:,1));
%% set up color map for display 
cmap = [1 1 1; ...% 1 - white - 空地
        0 0 0; ...% 2 - black - 障碍 
        1 0 0; ...% 3 - red - 已搜索过的地方
        0 0 1; ...% 4 - blue - 下次搜索备选中心 
        0 1 0; ...% 5 - green - 起始点
        1 1 0];...% 6 - yellow -  到目标点的路径 
colormap(cmap); 
map = zeros(25); 
% 设置障碍
for j=1:numofobs
    xobs(j) = obs(j,1);
    yobs(j) = obs(j,2);
    map(xobs(j),yobs(j)) = 2;
end
map(1,25) = 5; % 起始点
map(25,1) = 6; % 目标点
image(1.5,1.5,map);
grid on;
axis image;
%% 
nrows = 25; 
ncols = 25; 
start_node = sub2ind(size(map), 1, 25); 
dest_node = sub2ind(size(map), 25, 1); 
% Initialize distance array 
distanceFromStart = Inf(nrows,ncols); 
distanceFromStart(start_node) = 0; 
% For each grid cell this array holds the index of its parent 
parent = zeros(nrows,ncols); 
t0=clock;
% Main Loop 
while true 
 % Draw current map 
 map(start_node) = 5; 
 map(dest_node) = 6; 
 image(1.5, 1.5, map); 
 grid on; 
 axis image; 
 drawnow; 
  % Find the node with the minimum distance 
 [min_dist, current] = min(distanceFromStart(:)); 
  if ((current == dest_node) || isinf(min_dist)) 
       break; 
  end; 

 map(current) = 3; 
 distanceFromStart(current) = Inf; 
 [i, j] = ind2sub(size(distanceFromStart), current);
 neighbor = [i-1,j;... 
            i+1,j;... 
            i,j+1;... 
            i,j-1] 
outRangetest = (neighbor(:,1)<1) + (neighbor(:,1)>nrows) +...
                   (neighbor(:,2)<1) + (neighbor(:,2)>ncols ) 
locate = find(outRangetest>0); 
neighbor(locate,:)=[] 
neighborIndex = sub2ind(size(map),neighbor(:,1),neighbor(:,2)) 
for i=1:length(neighborIndex) 
if (map(neighborIndex(i))~=2) && (map(neighborIndex(i))~=3 && map(neighborIndex(i))~= 5) 
    map(neighborIndex(i)) = 4; 
  if distanceFromStart(neighborIndex(i))> min_dist + 1      distanceFromStart(neighborIndex(i)) = min_dist+1; 
        parent(neighborIndex(i)) = current; 
  end 
 end 
end 
end
TimeCost=etime(clock,t0)
%%
if (isinf(distanceFromStart(dest_node))) 
    route = []; 
else 
    %提取路线坐标
   route = [dest_node]; 
      while (parent(route(1)) ~= 0) 
              route = [parent(route(1)), route]; 
       end 
  % 动态显示出路线     
        for k = 2:length(route) - 1 
          map(route(k)) = 7; 
                pause(0.1); 
                image(1.5, 1.5, map); 
              grid on; 
              axis image; 
              end 
end
axis off;

7 obsdata.txt

10 1 0.5
20 1 0.5
21 1 0.5
17 2 0.5
18 2 0.5
1 3 0.5
5 3 0.5
18 3 0.5
3 4 0.5
9 4 0.5
15 4 0.5
22 4 0.5
23 4 0.5
2 5 0.5
7 5 0.5
9 5 0.5
13 5 0.5
18 5 0.5
3 6 0.5
7 6 0.5
24 7 0.5
5 7 0.5
9 7 0.5
18 7 0.5
13 8 0.5
15 8 0.5
5 9 0.5
19 9 0.5
21 9 0.5
6 11 0.5
11 11 0.5
16 11 0.5
17 11 0.5
2 12 0.5
11 12 0.5
19 12 0.5
5 14 0.5
12 14 0.5
13 14 0.5
5 15 0.5
2 16 0.5
7 16 0.5
10 16 0.5
18 16 0.5
5 17 0.5
11 17 0.5
21 17 0.5
23 17 0.5
16 18 0.5
2 19 0.5
9 19 0.5
17 19 0.5
24 19 0.5
5 20 0.5
13 20 0.5
15 20 0.5
16 20 0.5
21 20 0.5
25 20 0.5
3 21 0.5
4 21 0.5
7 21 0.5
15 21 0.5
20 21 0.5
24 21 0.5
6 22 0.5
5 23 0.5
9 23 0.5
11 23 0.5
16 23 0.5
20 23 0.5
23 23 0.5
4 25 0.5
9 25 0.5
18 25 0.5

参考文献：

【1】最短路径问题---Dijkstra算法详解