图论：Dijkstra算法——最详细的分析，图文并茂，一次看懂！

【 1. Dijkstra算法简介 】

• 背景
  迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄杰斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。
• 用途
  该算法可以算出从一个顶点到其余各顶点的最短路径，解决的是有权图中最短路径问题。
• 复杂度
  $该算法复杂度=n^2$
• 核心思想
  迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。
• Dijkstra算法理解
  Dijkstra算法是一种标号法：给赋权图的每一个顶点记一个数，称为顶点的标号：临时标号T 表示从始顶点到该标点的最短路长的上界、固定标号P 表示从始顶点到该顶点的最短路长。
  

【 2. 算法实现范例 】

• 求始点$V_1$到其余顶点的最短路径
  

• 令不可直接到达$V_1$的点（需经过第三个点）到$V_1$的距离为 ∞ 。
  此时，距$V_1$最近的点：$V_1$，最短路径：$V_1$→$V_1$，最短距离：0。
  
  

• 除自身外，距离$V_1$最近的点：$V_4$。可知，最短路径：$V_1\to V_4$，最短距离：1。
  
  

• 由上步已获知$V_1$到$V_4$的最短路径，则：
  $V_1$→$V_4$→$V_3$距离为8 = $V_1$→$V_3$的距离8，不更新表格 ；
  $V_1$→$V_4$→$V_7$距离为10< ∞，更新表格。

更新表格后，距离$V_1$最近的点：$V_2$。可知，最短路径：$V_1\to V_2$，最短距离：2。

• 由上步已获知$V_1$到$V_2$的最短路径，则：
  $V_1$→$V_2$→$V_3$距离为8 =8，不更新表格。
  $V_1$→$V_2$→$V_5$距离为3 < ∞，更新表格。
  
  更新表格后，距离$V_1$最近的点：$V_5$。可知，最短路径：$V_1\to V_2\to V_5$，最短距离：3。

• 由上步已获知$V_1$到$V_5$的最短路径，则：
  $V_1$→$V_2$→$V_5$→$V_3$距离为 8 = 8，不更新表格。
  $V_1$→$V_2$→$V_5$→$V_6$距离为 6 < ∞，更新表格。
  $V_1$→$V_2$→$V_5$→$V_9$距离为 12 < ∞，更新表格。
  $V_1$→$V_2$→$V_5$→$V_8$距离为 5 < ∞，更新表格。
  
  更新表格后，距离$V_1$最近的点：$V_8$。可知，最短路径：$V_1\to V_2\to V_5\to V_8$，最短距离：5。
  
  
• 由上步已获知$V_1$到$V_8$的最短路径，则：
  $V_1$→$V_2$→$V_5$→$V_8$→$V_9$距离为 12 =12，不更新表格。
  $V_1$→$V_2$→$V_5$→$V_8$→$V_{1}1$距离为 14 < ∞，更新表格。
  
  更新表格后，距离$V_1$最近的点：$V_6$。可知，最短路径：$V_1\to V_2\to V_5\to V_6$，最短距离：6。
  

• 由上步已获知$V_1$到$V_6$的最短路径，则：
  $V_1$→$V_2$→$V_5$→$V_6$→$V_7$距离为 10=10，不更新表格。
  $V_1$→$V_2$→$V_5$→$V_6$→$V_9$距离为 12=12，不更新表格。
  $V_1$→$V_2$→$V_5$→$V_6$→$V_3$距离为 7<8，更新表格。
  
  更新表格后，距离$V_1$最近的点：$V_3$。可知，最短路径：$V_1\to V_2\to V_5\to V_6\to V_3$，最短距离：7。
  
  
• 由上步已获知$V_1$到$V_3$的最短路径，则：
  $V_1\to V_2\to V_5\to V_6\to V_3\to V_7$距离为 9<10，更新表格。
  
  更新表格后，距离$V_1$最近的点：$V_7$。可知，最短路径：$V_1\to V_2\to V_5\to V_6\to V_3\to V_7$，最短距离：9。
  
  
• 由上步已获知$V_1$到$V_7$的最短路径，则：
  $V_1\to V_2\to V_5\to V_6\to V_3\to V_7\to V_9$距离为 12<11，不更新表格。
  $V_1\to V_2\to V_5\to V_6\to V_3\to V_7\to V_{10}$距离为 10<∞，更新表格。
  
  更新表格后，距离$V_1$最近的点：$V_{10}$。可知，最短路径：$V_1\to V_2\to V_5\to V_6\to V_3\to V_7\to V_{10}$，最短距离：10。
  
• 由上步已获知$V_1$到$V_{1}0$的最短路径，则：
  $V_1\to V_2\to V_5\to V_6\to V_3\to V_7\to V_{10}\to V_{11}$距离为 14<11，不更新表格。
  $V_1\to V_2\to V_5\to V_6\to V_3\to V_7\to V_{10}\to V_9$距离为 11<12，更新表格。
  
  此时，距离$V_1$最近的点：$V_9$。可知，最短路径：$V_1\to V_2\to V_5\to V_6\to V_3\to V_7\to V_{10}\to V_9$，最短距离：11。
  
• 由上步已获知$V_1$到$V_9$的最短路径，则：
  $V_1\to V_2\to V_5\to V_6\to V_3\to V_7\to V_{10}\to V_9\to V_{11}$距离为 13<14，更新表格。
  
  此时，距离$V_1$最近的点：$V_{11}$。可知，最短路径：$V_1\to V_2\to V_5\to V_6\to V_3\to V_7\to V_{10}\to V_9\to V_{11}$，最短距离：13。
  
  

【 3. 邻接矩阵 】

邻接矩阵用于描述图上顶点间的关系。例如临接矩阵$D[i][j]$表示顶点 i 到顶点 j 的直达距离，可将其赋值为无穷大 Inf 来表示顶点 i 无法直达到顶点 j 。

【 4. Dijkstra 算法的 C++ 描述 】

/*
函数名：dijkstra()  迪科斯彻最短路径算法 
参数：vs：源点的索引;f：终点的索引;
      pre[]：前驱数组,即pre[i]为从vs到i最短路径时,i前面那个顶点的索引 
	  dist[]：距离数组，即dist[i]是vs到i的最短路径的长度 
全局变量q：点的数量 
功能：算出从源点下标vs到其余点最短路径,轨迹记录在pre[],距离记录在dist[]。 
*/
void dijkstra(  int vs, int prev[], int dist[],int f )
{   
    
    int i,j,k,g;
    int min;
    int tmp;
    int flag[q];  // flag[i]=1表示"顶点vs"到"顶点i"的最短路径已成功获取。
    g=0;
    getweight();
/* 1.  初始化*/
    for (i = 0; i < q; i++)
    {
        flag[i] = 0;  // 顶点i的最短路径还没获取到。
        prev[i] = vs;  // 顶点i的前驱顶点为0。
        dist[i] = martix[vs][i];// 顶点i的最短路径为vs到i的权。
    }
 					 
    flag[vs] = 1; // 对顶点vs自身进行初始化
    dist[vs] = 0; 
 
/* 2.  遍历q-1次，每次找出vs到另一个顶点的最短路径 */
    for (i = 1; i < q ; i++)
    {
        
        /* 2.1 在未获取最短路径的顶点中，找到离vs最近的顶点k */
        min = INF;
        for ( j = 0; j < q ; j++)
        {
            if (flag[j]==0 && dist[j]<min)
			//若从vs到顶点j距离小于min,而且从vs到j的最短路径还未获取。 
            {
                min = dist[j];//改变最近距离 
                k = j;//记录j 
            }
        }
        
       /* 2.2  对刚刚已找到最短距离的顶点k进行标记判断     */
        flag[k] = 1; // 标记顶点k,dist[k]已确定。 
        if(k==f)   //判断k是否是终点索引,若是则退出 
			break;
	
        /*  2.3   已知顶点k的最短路径后,更新未获取最短路径的顶点的最短路径和前驱顶点   */
        for (j = 0; j < q ; j++)
        {
            tmp = (martix[k][j]==INF ? INF : (min + martix[k][j])); // 防止溢出
            if (flag[j] == 0 && (tmp  < dist[j]) ) //若j还不是最短距离且从k到j距离比记录的距离短 
            {
			    prev[j] = k;  //更新k的前驱和最短距离 
                dist[j] = tmp;
            }
        }
        
    }
 
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

【 5. Dijkstra 算法的 Matlab 描述 】

两个文件在同一文件夹下，运行 tulun1.m 即可。

% 文件命名为：tulun1.m
weight=    [0     2     8     1   Inf   Inf   Inf   Inf   Inf   Inf   Inf;
            2     0     6   Inf     1   Inf   Inf   Inf   Inf   Inf   Inf;
            8     6     0     7     5     1     2   Inf   Inf   Inf   Inf;
            1   Inf     7     0   Inf   Inf     9   Inf   Inf   Inf   Inf;
          Inf     1     5   Inf     0     3   Inf     2     9   Inf   Inf;
          Inf   Inf     1   Inf     3     0     4   Inf     6   Inf   Inf;
          Inf   Inf     2     9   Inf     4     0   Inf     3     1   Inf;
          Inf   Inf   Inf   Inf     2   Inf   Inf     0     7   Inf     9;
          Inf   Inf   Inf   Inf     9     6     3     7     0     1     2;
          Inf   Inf   Inf   Inf   Inf   Inf     1   Inf     1     0     4;
          Inf   Inf   Inf   Inf   Inf   Inf   Inf     9     2     4     0;];
[dis, path]=dijkstra(weight,1, 11)
1
2
3
4
5
6
7
8
9
10
11
12
13

% 文件命名为：dijkstra.m
function [min,path]=dijkstra(w,start,terminal)
n=size(w,1); label(start)=0; f(start)=start;
for i=1:n
   if i~=start
       label(i)=inf;
end, end
s(1)=start; u=start;
while length(s)<n
   for i=1:n
      ins=0;
      for j=1:length(s)
         if i==s(j)
            ins=1;
         end,  
      end
      if ins==0
         v=i;
         if label(v)>(label(u)+w(u,v))
            label(v)=(label(u)+w(u,v)); 
         f(v)=u;
         end, 
      end, 
   end   
v1=0;
   k=inf;
   for i=1:n
         ins=0;
         for j=1:length(s)
            if i==s(j)
               ins=1;
            end, 
         end
         if ins==0
            v=i;
            if k>label(v)
               k=label(v);  v1=v;
            end,  
         end,  
   end
   s(length(s)+1)=v1;  
   u=v1;
end
min=label(terminal); path(1)=terminal;
i=1; 
while path(i)~=start
      path(i+1)=f(path(i));
      i=i+1 ;
end
path(i)=start;
L=length(path);
path=path(L:-1:1);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

【 6. 温故知新！ 】

------------------------------------------------------------------分割线-------------------------------------------------------------------
2020/10/17，翻新总结

1. 第一步，定义个邻接矩阵 Martix[ ][ ]， Martix[i][j] 代表点 i 到 点 j 的初始距离，若点 i 能直达到点 j （不经过第三个点），则 Martix[i][j]=对应距离，否则=无穷大。
2. 第二步，定义3个数组存信息
   距离数组dist[ ]，dist[i]代表源点 vs 到点 i 的最短路径的长度；
   再定义个前驱数组 pre[ ]，pre[i]代表源点 vs 到点 i 的最短路径的前驱点（即上一个点）。
   最后再定义个标记数组flag[ ]，flag [i]=1 代表源点vs到点i的最短距离已经确定。
3. 好了，前戏准备完毕，进入正题，让我们开始初始化第二步定义的三个数组。
   显而易见，dist[vs]=0，自己到自己距离为0，那么其他的点嘛比如点 i ,.就让点vs到点 i 的距离等于Martix[vs][i]，即第一步的初始距离。
   那么前驱数组pre[ ] ，就让他们的前驱点都是点vs好了；
   最后这个标记位数组flag[ ] ，flag[vs]=1(自己到自己距离为0肯定最小了)，其他的都不确定，就flag[ 除点vs外的点 ]=0。
4. 初始化完毕。准备开炮。
   我们决定每遍历一次就确定vs到一个点的最短路径，那么需要遍历n-1次（算上点vs共有n个点嘛）。
   也就是每次遍历我们都需要找到距离点vs最近的点（怎么找？同样遍历个n-1次来比较没确定最短路径的点的dist [ ] 哪个最小 ），此时肯定是最短路径啊（你经过别的点再绕向它距离肯定大了），那么这个点的flag[i] =1,dist[i] 确定不变了，pre[i] 也不变了。
5. OK，我们已经确定了一个最短路径。那么开始刷新吧。
   刷新的是什么呢？确定一个最短路径后，可能这个点 i 到其他点的距离<原来点vs到点 i 的距离，所以我们要刷新，dist [ ] 和 pre [ ]。
6. 好的，第5步刷新完了，就继续回到第四步不断遍历，直到所有的点都遍历完，那么最终的flag [ ] 都等于1了，dist [ ] 、pre [ ] 也存着你想要的信息。
7. 最重要的，完结，撒花✿✿ヽ(°▽°)ノ✿。