深入分析（迪杰斯特拉算法） Dijkstra 算法实现原理

╰半夏微凉° 2023-06-08 06:20 17阅读 0赞

迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个节点到其他节点的最短路径。  
它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。  
**基本思想**

通过Dijkstra计算图G中的最短路径时，需要指定起点s(即从顶点s开始计算)。

此外，引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)。

初始时，S中只有起点s；U中是除s之外的顶点，并且U中顶点的路径是"起点s到该顶点的路径"。然后，从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。 然后，再从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。 ... 重复该操作，直到遍历完所有顶点。

**操作步骤**

**(1)** 初始时，S只包含起点s；U包含除s外的其他顶点，且U中顶点的距离为"起点s到该顶点的距离"\[例如，U中顶点v的距离为(s,v)的长度，然后s和v不相邻，则v的距离为∞\]。

**(2)** 从U中选出"距离最短的顶点k"，并将顶点k加入到S中；同时，从U中移除顶点k。

**(3)** 更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离，是由于上一步中确定了k是求出最短路径的顶点，从而可以利用k来更新其它顶点的距离；例如，(s,v)的距离可能大于(s,k)+(k,v)的距离。

**(4)** 重复步骤(2)和(3)，直到遍历完所有顶点。

单纯的看上面的理论可能比较难以理解，下面通过实例来对该算法进行说明。

如下图有权图，**Dijkstra**算法可以计算**任意节点**到**其他节点**的最短路径

![format_png][]

**算法图解**

1.选定A节点并初始化，如上述步骤3所示

![format_png 1][]

2.执行上述 4、5两步骤，找出U集合中路径最短的节点D 加入S集合，并根据条件 `if ( 'D 到 B,C,E 的距离' + 'AD 距离' < 'A 到 B,C,E 的距离' )` 来更新U集合

![format_png 2][]

3.这时候 `A->B, A->C` 都为3，没关系。其实这时候他俩都是最短距离，如果从算法逻辑来讲的话，会先取到B点。而这个时候 if 条件变成了 `if ( 'B 到 C,E 的距离' + 'AB 距离' < 'A 到 C,E 的距离' )` ，**如图所示这时候`A->B`距离 其实为 `A->D->B`**

![format_png 3][]

1.  思路就是这样，往后就是大同小异了

![format_png 4][]

1.  算法结束

![format_png 5][]

**c\# 代码实现**

using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    
    namespace 迪杰斯特拉算法
    {
        struct Graph 
        {
            public char[] vexs;            // 顶点集合
            public int vexnum;             // 顶点数
            public int edgnum;             // 边数
            public int[,] matrix;          // 邻接矩阵
        };
    
        class Program
        { 
            static void Main(string[] args)
            {
                Graph g;
                g.vexs = new char[]{'A','B','C','D','E'};
                g.vexnum = 5;
                g.edgnum = 7;
                g.matrix = new int[5,5]{
                    {0,4,int.MaxValue,2,int.MaxValue},
                    {4,0,4,1,int.MaxValue},
                    {int.MaxValue,4,0,1,3},
                    {2,1,1,0,7},
                    {int.MaxValue,int.MaxValue,3,7,0}
                };
    
                dijkstra(g,0);
    
                Console.ReadKey();
    
            }
            private static void dijkstra(Graph g,int vs)
            {
                int k = vs;
                int min = int.MaxValue;
                int tmp;
                int[] flag = new int[100];             // flag[i]=1表示"顶点vs"到"顶点i"的最短路径已成功获取。
                int[] dist = new int[100];
                int[] prev = new int[100];
    
                for (int i = 0; i < g.vexnum; i++)
                {
                    flag[i] = 0;                          // 顶点i的最短路径还没获取到。
                    prev[i] = 0;                          // 顶点i的前驱顶点为0。
                    dist[i] = g.matrix[vs, i];            // 顶点i的最短路径为"顶点vs"到"顶点i"的权。
                }
    
                // 对 vs 进行初始化
                flag[vs] = 1;
                dist[vs] = 0;
    
                for (int i = 1; i < g.vexnum; i++)
                {
                    min = int.MaxValue;
                    for (int j = 0; j < g.vexnum; j++)
                    {
                        if (flag[j] == 0 && dist[j] < min)
                        {
                            min = dist[j];
                            k = j;
                        }
                    }
    
                    flag[k] = 1;
    
                    for (int n = 0; n < g.vexnum; n++)
                    {
                        tmp = g.matrix[k, n] == int.MaxValue ? int.MaxValue : (min + g.matrix[k, n]);
                        if (flag[n] == 0 && tmp < dist[n])
                        {
                            dist[n] = tmp;
                            prev[n] = k;
                        }
                    }
    
                }
    
                for (int i = 0; i < g.vexnum; i++)
                {
                    Console.WriteLine("点：" + g.vexs[vs] + " 到点：" + g.vexs[i] + "的最短距离为：" + dist[i]);
                }
    
            }
        }
    
    
    }

运行结果

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTMxNjgyNA_size_16_color_FFFFFF_t_70][]

[format_png]: /images/20230531/897168c1fb1345b4a3cc1908ae04cec2.png
[format_png 1]: /images/20230531/82ab3ab054574d9fa7991f629a148801.png
[format_png 2]: /images/20230531/ea1564db17294792b7850fd3013fa5df.png
[format_png 3]: /images/20230531/5c02e63ffc95429490e944af7c3f08d2.png
[format_png 4]: /images/20230531/d3e755b7682541209d653b430fa8ce6b.png
[format_png 5]: /images/20230531/d18dab27852c4f97bfde16e9a9b43b33.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTMxNjgyNA_size_16_color_FFFFFF_t_70]: /images/20230531/75e8ae0faaf048ebacbeaa71b9ecdea1.png