大黑书《离散数学及其应用》之Dijkstra算法

一、引言

        引言部分为概述性内容，可以跳过(写这部分的原因主要是避免CSDN发文助手的不聪明检测)。在本部分中，我将介绍最短路径算法、Dijkstra算法、Floyd算法。

        最短路径算法。最短路径算法主要分为两种，一种是单源最短路径算法，另一种是多源最短路径算法。在单源最短路径算法中，是在给定一个带权连通图(且权重为正数)下，求某一个顶点到其他所有顶点的最短路径长度。而在多源最短路径算法中，也是在给定一个带权连通图下，求图中任意顶点到其他所有顶点的最短路径长度。

        Dijkstra算法。Dijkstra算法是由荷兰计算机科学家狄克斯特拉（Dijkstra）于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。 其基本原理是：每次新扩展一个距离最短的点，更新与其相邻的点的距离。当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。不过根据这个原理，用Dijkstra求最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的距离，有可能就破坏了已经更新的点距离不会改变的性质。来源：MBA智库百科。

        Floyd算法。Floyd算法是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。在Floyd算法中，边权可正可负。来源：百度百科。

二、Dijkstra算法

        在《离散数学及其应用》中，Dijkstra算法如下

        在该算法中，S是一个集合，书中说表示一个特殊顶点集（按照我的理解是，当源点a到某个顶点v的最短路径长度确定时，v就被加入这个集合中）；L(v)是源点a到顶点v的最短路径长度。

        算法的输入为一个带权连通图，即顶点集、带权邻接矩阵w和源点a。

        在初始化阶段：L(v)被赋予无穷大，L(a)被赋予0；S被赋予空集。

        在算法的核心步骤中（从while z∉S开始到最后），算法主要更新L(v)的值和S。

        而算法的输出是L(z)，即包含了a到各顶点的最短路径长度的一个列表。

三、示例

        单看算法是很难理解这个算法的，我就结合自己的理解给这个算法做一个简单的示例吧。

        1、问题描述

        如下图所示的带权图中，顶点a与顶点z之间的最短通路的长度是多少？

        2、问题求解(巨详细版)

        现在我们就根据上面的Dijkstra算法对上述问题进行求解。求解步骤分别为：算法输入、初始化、核心步骤求解和输出。

        ①算法输入

        G = ，权重映射w。其中，

        V = {a，b，c，d，e，z}；// 节点集

        E = {(a,b)，(a,d)，(d,e)，(b,e)，(b,c)，(c,z)，(e,z)}；// 边集

        权重映射w：对于存在的边，w(a,b) = 4，w(a,d) = 2，w(d,e) = 3，w(b,e) = 3，w(b,c) = 3，w (c,z) =2，w(e,z) = 1；对于不存在的边(i，j)（i，j∈V），w(i,j) = ∞。

        ②算法初始化

        L(a)=∞，L(b)=∞，L(c)=∞，L(d)=∞，L(e)=∞，L(z)=∞；// L存储a到各顶点的最短路径

        L(a)=0；

        S=∅；

        ③算法核心步骤求解过程 (建议自己在草稿纸上画一个图结合看)

        当顶点z∉S时，执行以下步骤。

        第一轮(S=∅，z∉S，执行)：

        (1) L(a)=0,L(b)=∞,L(c)=∞,L(d)=∞,L(e)=∞,L(z)=∞,S=∅ // L(a)最小且a∉S,选择节点a；

        (2) 把a加入S,S={a}；

        (3) 所有不属于S={a}的顶点有：b、c、d、e、z

                b：L(a)+w(a,b)=0+4=4，比L(b)=∞更小，更新L(b)=4；

                c：L(a)+w(a,c)=0+∞=∞，不比L(c)=∞更小，不更新L(c)；

                d：L(a)+w(a,d)=0+2=2，比L(d)=∞更小，更新L(d)=2；

                e：L(a)+w(a,e)=0+∞=∞，不比L(e)=∞更小，不更新L(e)；

                z：L(a)+w(a,z)=0+∞=∞，不必L(z)=∞更小，不更新L(z)；

        根据上面的更新，L(a)=0,L(b)=4,L(c)=∞,L(d)=2,L(e)=∞,L(z)=∞。

        第二轮(S={a}，z∉S，执行)：

        (1) L(a)=0,L(b)=4,L(c)=∞,L(d)=2,L(e)=∞,L(z)=∞,S={a} // L(d)最小且d∉S,选择节点d；

        (2) 把d加入S,S={a,d}；

        (3) 所有不属于S={a,d}的顶点有：b、c、e、z

                b：L(d)+w(d,b)=2+∞=∞，不比L(b)=4更小，不更新L(b)；

                c：L(d)+w(d,c)=2+∞=∞，不比L(c)=∞更小，不更新L(c)；

                e：L(d)+w(d,e)=2+3=5，比L(e)=∞更小，更新L(e)=5；

                z：L(d)+w(d,z)=2+∞=∞，不比L(z)=∞更小，不更新L(z)；

        根据上面的更新，L(a)=0,L(b)=4,L(c)=∞,L(d)=2,L(e)=5,L(z)=∞。

        第三轮(S={a,d}，z∉S，执行)：

        (1) L(a)=0,L(b)=4,L(c)=∞,L(d)=2,L(e)=5,L(z)=∞,S={a,d} // L(b)最小且b∉S,选择节点b；

        (2) 把b加入S,S={a,d,b}；

        (3) 所有不属于S={a,d,b}的顶点有：c、e、z

                c：L(b)+w(b,c)=4+3=7，比L(c)=∞更小，更新L(c)=7；

                e：L(b)+w(b,e)=4+3=7，不比L(e)=5更小，不更新L(e)；

                z：L(b)+w(b,z)=4+∞=∞，不比L(z)=∞更小，不更新L(z)；

        根据上面的更新，L(a)=0,L(b)=4,L(c)=7,L(d)=2,L(e)=5,L(z)=∞。

        第四轮(S={a,d,b}，z∉S，执行)：

        (1) L(a)=0,L(b)=4,L(c)=7,L(d)=2,L(e)=5,L(z)=∞,S={a,d,b} // L(e)最小且e∉S,选择节点e；

        (2) 把e加入S,S={a,d,b,e}；

        (3) 所有不属于S={a,d,b,e}的顶点有：c、z

                c：L(e)+w(e,c)=5+∞=∞，不比L(c)=7更小，不更新L(c)；

                z：L(e)+w(e,z)=5+1=6，比L(z)=∞更小，更新L(z)=6；

        根据上面的更新，L(a)=0,L(b)=4,L(c)=7,L(d)=2,L(e)=5,L(z)=6。

        第五轮(S={a,d,b,e}，z∉S，执行)：

        (1) L(a)=0,L(b)=4,L(c)=7,L(d)=2,L(e)=5,L(z)=6,S={a,d,b} // L(z)最小且z∉S,选择节点z；

        (2) 把z加入S,S={a,d,b,e,z}；

        (3) 所有不属于S={a,d,b,e,z}的顶点有：c

                c：L(z)+w(z,c)=6+2=8，不比L(c)=7更小，不更新L(c)；

        根据上面的更新(实际上没有更新)，L(a)=0,L(b)=4,L(c)=7,L(d)=2,L(e)=5,L(z)=6。

        第六轮(S={a,d,b,e,z}，z∈S，不执行，跳出循环)

        ④算法输出

        算法输出是L(z)=6，即顶点a到顶点z的最短路径长度。

        3、问题求解(简洁版)

        贴一下图，免得大家翻页太麻烦。

        求解过程如下：其中红色箭头表示了S和L的变化与更新。

        4、练习题：求a到z的最短路径长度。

        答案：13.

四、个人思考

        1、从上面给出的算法中，Dijkstra算法只能找到a到其他顶点的最短路径长度，而无法找到源点a到其他顶点的最短路径。如果要找到路径，我觉得要考虑更加复杂的变量在其中。

        2、从上面给出的算法中，Dijkstra算法并没有求源点a到其他所有顶点的最短路径长度，而是求到z就算法终止了。其中示例中所求到的最短路径长度包括a到S中的任意一个顶点，而不包括c。按照我的理解，当算法的循环条件设为while |S|!=|V|的时候，我觉得可以求a到其他所有顶点的最短路径长度。

        3、Dijkstra算法是动态规划类型的算法吗？是，因为L(v)的更新条件是

        具有动态规划中的最优子结构。

五、参考

        1、离散数学及其应用，Kenneth H. Rosen，机械工业出版社；

        2、百度百科；

        3、智库百科；

        4、知乎博文：Dijkstra算法。