迪杰斯特拉（Dijkstra)算法最通俗易懂的讲解

朴灿烈づ我的快乐病毒、 2022-03-06 16:08 491阅读 0赞

一、问题定义

求解单元点的最短路径问题：给定带权有向图G和源点v，求v到G中其他顶点的最短路径

限制条件：图G中不存在负权值的边

二、思想

划重点，迪杰斯特拉最最朴素的思想就是按长度递增的次序产生最短路径。即每次对所有可见点的路径长度进行排序后，选择一条最短的路径，这条路径就是对应顶点到源点的最短路径。

Tips：可见点就是从源点开始按广度优先算法遍历顶点的过程中，搜索到的点。

下面来解释一下为什么源点到所有可见点的路径中长度最短的一条就一定是源点到该点的最短路径，会不会存在通过一些当前不可见的点间接到达该点的路径比它短呢？

我们设图G的顶点集合为V，再设一个集合S表示已求得最短路径的终点的集合（S怎么来的下面再说）。

设下一条最短路径（终点为x），那么它只能是弧（v，x）或者通过S中的顶点到达x即（v，vi,....,x）。我们来证明一下：

假设（v，...,x）路径上有一个顶点不在S中，则说明存在一条终点不在S中而长度比此路径还短的路径。但这是不可能的。因为我们按长度递增的顺序来产生各最短路径，所以长度比此路径还短的所有路径均已产生，他们的终点一定在S中。

三、算法

1.初始化。V为G中所有顶点集合，S=\{v\}。D\[x\]表示从源点到x的已知路径，初始D\[v\]为0，其余为无穷大。

2.从源点v开始运行一步广度优先算法即找其相邻点。如下图中从源点0开始，找到的可见点为1,2,3.

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvb2R4aW5faWU_size_16_color_FFFFFF_t_70][]

3.计算可见点到源点v的路径长度，更新D\[x\]。然后对路径进行排序，选择最短的一条作为确定找到的最短路径，将其终点加入到S中，如此处找到的点为2，故将2加入S。S=\{v，2\}.

4.从S中选择新加入的点运行广度优先算法找其相邻点，重复step3。直至所有点已加入S或者再搜索不到新的可见点（图中存在不联通的点，此时S<V）终止算法。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvb2R4aW5faWU_size_16_color_FFFFFF_t_70 1][]

总结一下：

迪杰斯特拉算法总共就干了两件事：

【1】不断运行广度优先算法找可见点，计算可见点到源点的距离长度

【2】从当前已知的路径中选择长度最短的将其顶点加入S作为确定找到的最短路径的顶点。

python实现如下：

def dijkstra(graph,v0):
        vNum = graph.numNode
        paths = {}
        count = 0
        cands = PQueue()
        cands.put((0,v0,v0))  #(pLen, u, vmin)表示经由u到vmin的已知最小路径长度为pLen
      
        while count < vNum and not cands.empty():
            pLen, u, vmin = cands.get()   #取出可见点到源点中路径最短的一条,由优先队列实现
            if vmin in paths.keys():
                continue
            paths[vmin] = (u,pLen)   #v0到vmin的最小路径长度为pLen，其前驱为u，记住前驱是为了通过回溯还原路径
    
            for v,w in graph.getOutEdges(vmin):  #找可见点
               if v not in paths.keys():
                   cands.put((pLen + w,vmin,v))   
            count += 1
        return paths

完整代码[https://download.csdn.net/download/goodxin\_ie/11045007][https_download.csdn.net_download_goodxin_ie_11045007]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvb2R4aW5faWU_size_16_color_FFFFFF_t_70]: /images/20220302/7e62542a3aa547809f008f21a4ecb280.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvb2R4aW5faWU_size_16_color_FFFFFF_t_70 1]: /images/20220302/d3159dd4ccb14273aba7b907ec7ee33d.png
[https_download.csdn.net_download_goodxin_ie_11045007]: https://download.csdn.net/download/goodxin_ie/11045007