最短路径算法之二：单源有权图，Dijkstra算法，python实现

关于单源、多源、权的解释，我的这篇文章有所介绍 ：

求单源无权图最短路径（pyhton）实现

本文仅讨论单源有权图，即给定起点，边带有权重的图。求单源有权图的最短路径，即求给定起点，到任意节点的最短路径。求这类图的常见算法就是Dijkstra算法。

Dijkstra算法

• 令 集合S = { 源点s + 已经确认了最短路径的顶点vi }
• 对任一未收录的顶点v，定义dist[v]为 s 到 v 的最短路径长度，该路径仅经过在集合S中的已经确认了最短路径的顶点。即 { s -> (vi ∈ S) -> v } 的最小长度。
• 如果路径是按照递增顺序生成的，那么有以下3个结论：
  1. ​​​真正的最短路只经过S中的顶点。为什么？假设存在一个未收录的顶点W使得S->V的路径不是最短，而是s->w + w->v的路径最短，那么 s->w 必然比 s->v 短，w 必然比 v 先被收录到S中，所以这是假命题。得到结论：真正的最短路只经过S中的顶点。
  2. 每次从未收录的定点中选一个dist 最小的收录（贪心思想）
  3. 每收录一个 v ，可能影响 v 的其他邻接结点的dist值。为什么呢？假设w是v的邻接节点，收录v前，根据结论1得出结论：dist[w]必然不经过v。收录v后，dist[w]可能经过v，所以dist[w]需要重新计算。dist[w] = min( dist[w], dist[v]+边的权重。

以下图为例：

 步骤详解：

确认起点为V1，并更新dist[V1]=0。

• 此时， S = {  }
• dist [] = [0, ∞, ∞, ∞, ∞, ∞, ∞,]

根据结论2开始循环，每次从未收录的定点中选一个dist 最小的收录，这样顶点就是按照dist递增的顺序被收录到S中。

从dist中找出一个未收录的、最短路径的顶点：V1，并收录到S中，同时更新该顶点到其他未收录的邻接点的dist

• V1 的邻接点有V2，V4，更新dist[V2] = min(2,∞) =2 , dist[V4] = (1, ∞) = 1
• 此时， S = { V1 }
• dist [] = [0, 2, ∞, 1, ∞, ∞, ∞,]

从dist中找出一个未收录的、最短路径的顶点：V4，并收录到S中，同时更新该顶点到其他未收录的邻接点的dist

• V4 的邻接点有V3、5、6、7，更新dist[V3] = min(1+2,∞) =3 ，dist[V5] = min(1+2,∞) =3，dist[V6] = min(1+8,∞) =9，dist[V7] = min(1+4,∞) =5
• 此时， S = { V1，V4 }
• dist [] = [0, 2, 3, 1, 3, 9, 5]

从dist中找出一个未收录的、最短路径的顶点：V2，并收录到S中，同时更新该顶点到其他未收录的邻接点的dist

• V2 的邻接点有V4、5，由于V4已经收录，忽略。dist[V5] = min(3, 2+10) =3，不变。
• 此时， S = { V1，V4，V2 }
• dist [] = [0, 2, 3, 1, 3, 9, 5]

从dist中找出一个未收录的、最短路径的顶点：V3，并收录到S中，同时更新该顶点到其他未收录的邻接点的dist

• V3 的邻接点有V1、6，由于V1已经收录，忽略。dist[V6] = min(9, 3+5) =8，发现了吗？dist[V6]变小了！就是说，新收录的节点会影响后续收录的节点的最小路径，这证明了结论3：每收录一个 v ，可能影响 v 的其他邻接结点的dist值
• 此时， S = { V1，V4，V2，V3 }
• dist [] = [0, 2, 3, 1, 3, 8, 5]

     

从dist中找出一个未收录的、最短路径的顶点：V5，并收录到S中，同时更新该顶点到其他未收录的邻接点的dist

• V5 的邻接点有V7，dist[V7] = min(5, 3+6) =5，不变。
• 此时， S = { V1，V4，V2，V3，V5}
• dist [] = [0, 2, 3, 1, 3, 8, 5]

从dist中找出一个未收录的、最短路径的顶点：V7，并收录到S中，同时更新该顶点到其他未收录的邻接点的dist

• V7 的邻接点有V6，dist[V6] = min(8, 5+1) =6，dist变小了，说明V1->V6的最短路径经过V7。
• 此时， S = { V1，V4，V2，V3，V5，V7}
• dist [] = [0, 2, 3, 1, 3, 6, 5]

从dist中找出一个未收录的、最短路径的顶点：V6，并收录到S中，同时更新该顶点到其他未收录的邻接点的dist

• V6 的没有邻接点。
• 此时， S = { V1，V4，V2，V3，V5，V7，V6}
• dist [] = [0, 2, 3, 1, 3, 6, 5]

最后，所有节点都已经被S收录，算法到这里就结束了。求得以V1为源点，到其他顶点V的距离为 dist [] = [0, 2, 3, 1, 3, 6, 5]

最后，我们用代码来实现一下：

class DijkstraHeap(IVisitGraph):
    """
    dijkstra算法求最短路径
    min dist 用最小堆实现
    """
 
    INFINITY = 9999999
 
    def __init__(self):
        """
        起点
        """
        super(DijkstraHeap, self).__init__()
        self.collected = []
        self.dist = []
        self.s = None  # 起点
        self.g = None  # 图
 
    def initVisted(self, g):
        super(DijkstraHeap, self).initVisted(g)
        # 初始化最短路径数组，所有顶点都是勿穷大
        self.dist = [self.INFINITY for i in range(g.nV)]          
        # 初始化收录数组，所有顶点均未收录
        self.collected = [False for i in range(g.nV)]  
 
    def visit(self, g, v: int):
        """
        dijkstra 算法，求图单源带权最短路
        g: 图，矩阵实现
        v: 起点
        """
        self.s = v  # dijkstra算法是单源的，必须确认起点
        self.g = g  # 图也是固定的
        self.dist[v] = 0  # 初始化顶点dist为0，自己到自己是0
 
        elements = [VNode(index=i, weight=weight) for i, weight in enumerate(self.dist)]
        minDistHeap = ElementMinHeap().buildHeap(elements=elements)  # 建立dist最小堆
 
        while not minDistHeap.isEmpty():
 
            # 从dist中选出一个未访问的，路径最短的节点
            V = minDistHeap.deleteMin()
 
            # 加入集合中
            self.collected[V.index] = True
 
            # 更新其他邻接顶点的 dist
            for i, val in enumerate(g.G[V.index]):
                if g.G[V.index][i] == -1:  # 没有边
                    continue
                if self.collected[i]:  # 已收录
                    continue
                
                # 判断新收录顶点V是否影响其邻接节点的dist
                # dist[i] = min(dist[i], dist[V]+权重)
                if self.dist[V.index]+g.G[V.index][i] < self.dist[i]:
                    self.dist[i] = self.dist[V.index]+g.G[V.index][i]
                    # 别忘了调整堆，堆是根据dist建的，dist变化了，堆也要调整
                    minDistHeap.updateX(i, self.dist[i])