🎈 作者：Linux猿

🎈 简介：CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、面试、刷题、算法尽管咨询我，关注我，有问题私聊！

🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬

今天给大家讲解下考研常考知识点最短路径Dijkstra算法，Dijkstra算法经常出现在试卷第三大题解答题中，是出题人比较青睐的出题点，而且可以结合深度优先搜索和广度优先搜索来进行考查，需要重点关注，接下来为大家讲解下Dijkstra算法。

图 1

一、Dijkstra算法可以解决哪些问题？

可以解决一个源点到一个或多个终点的问题。如上图所示，假设源点为V0，Dijkstra可以求解从V0到图中一个或多个终点的最短距离或路径。

二、算法思想

前提：

假设图中有n个顶点，源点为V0，二维数组g[][]存储各顶点之间的权值，从V0到Vi的最短距离为D[i]，初始化为g[0][i]，即:D[i] = g[0][i]；

集合S为已经求解出的到V0最短距离的顶点集合，初始化时只包含顶点V0，即：S={v0}。

过程：

（1）选中当前距离V0最近的一点顶点Vk（Vk不属于集合S），使用如下公式：

因为我们已经有D[i]数组了，所以可以求得距离V0最近的一个顶点Vk。Vk与V0的关系是（V0,....,Vk），即V0到Vk中间可能有0个或多个中间结点。

（2）将Vk加入到集合S中，即S={V0,......,Vk}；

（3）使用Vk更新其它顶点到V0的最短距离，因为目前是Vk到V0的距离最短，当然使用Vk来更新啦，更新规则如下：

   如果 D[k] + g[k][j] < D[j] （Vj不属于集合S）成立，即：当前顶点Vj距离V0的最短距离D[j]，在经过以Vk作为中间结点后，距离更短了，则更新D[j]。其中，D[k]代表（V0,Vk）的距离，g[k][j]为（Vk，Vj）的距离，那么D[k]+g[k][j]为(V0,Vj)的距离。

   如果上式成立，则更新D[j]，如下：

即：将D[j]的距离更新。

   如果不成立，则不更新。

（4）继续执行（1）。

那么上面的循环执行多少次呢，当然是执行n-1次啦，因为除了源点，还有n-1个顶点可以选择呀，顶点都加入到集合S中了就代表最短路径完成了。

可能有的小伙伴还是没有理解上面的思想，不着急，接着往下看，结合源码你会有更深的体会。

三、源码解读

注意：集合S代表已经确定的顶点，这些顶点与源点之间的距离已经确定了，不再更新。

bool visited[Max_Size]; //标记顶点是否已经加入到集合S中

void Dijkstra(MGrap G, int v0, MinPath& D)

{

    for(int v = 0; v < G.vexnum; v++) //初始化所有顶点到源点的距离

    {

        visited[v] = false;

        D[v] = G.g[v0][v];

    }

D[v0] = 0; visited[v0] = true;// 设置源点

// 遍历n - 1次，求源点到其余n-1个顶点的最短距离

for(int i = 1; i < G.vexnum; ++i) 

{

        min = Max_Path; //设置一个无穷大的距离，以便寻找最近顶点

   //for循环选出不在集合S中，且距离V0最近的一个顶点


        for(int v = 0; v < G.vexnum; ++v)

            if(!visited[v] && D[v] < min)

            {

                k = v; min = D[v];

            }

        visited[k] = true;  //将选入的顶点标记,相当于放入集合S中

  //使用选入的顶点作为中间结点，对其它未选入的顶点到源点的距离进行更新

        for(int j = 0; j < G.vexnum; ++j)  

            if(!visited[j] && min + g[k][j] < D[j])

            {

                D[j] = min + g[k][j];

            }

    }

}

四、算法复杂度

时间复杂度：

从上面的源码中可以看到，主要时间是在求解路径时的for循环上，最外层的for循环为O(n)，里面是两个并列的for循环，所以是O(n)，因为内外两层for循环是嵌套的，所以总的时间复杂度为O(n²)。

空间复杂度：

算法使用到了一个邻接矩阵和一维数组，所以空间复杂度为O(n²)

五、总结

Dijkstra算法的讲解今天就到这里了，Dijkstra是一个考研常考内容，小伙伴们一定要做到熟练，另外，Dijkstra求解最短路径过程图和邻接矩阵的表示形式需要重点熟悉，我们会在接下来的文章中进行讲解。

CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、面试、刷题、算法尽管咨询我，关注我，有问题私聊！

欢迎小伙伴们点赞👍、收藏⭐、留言💬