【贪心算法】单源最短路径Python实现

文章目录

• • @[toc]
  • • 问题描述
    • `Dijkstra`算法
    • `Dijkstra`算法的正确性
    • • 贪心选择性质
      • 最优子结构性质
    • `Dijkstra`算法应用示例
    • `Python`实现
    • 时间复杂性

问题描述

• 给定一个带权有向图$G=(V,E)$，其中每条边的权是非负实数，给定$V$中的一个顶点，称为源
• 计算从源到所有其他各顶点的最短路径长度

Dijkstra算法

• Dijkstra算法是解单源最短路径问题的一个贪心算法
• 其基本思想是，设置顶点集合$S$，并不断地做贪心选择来扩充这个集合，一个顶点属于集合$S$当且仅当从源到该顶点的最短路径长度已知
• 初始时，$S$中仅含有源，设$u$是$G$的某一个顶点，把从源到$u$且中间只经过$S$中顶点的路称为从源到$u$的特殊路径，并用数组$dist$记录当前每个顶点所对应的最短特殊路径长度，用数组$parent[i]$记录从源到顶点$i$的最短路径上$i$的前一个顶点
• Dijkstra算法每次从$V-S$中取出具有最短特殊路长度的顶点$u$，将$u$添加到$S$中，同时对列表$dist$和$parent$做必要的修改，当$dist[u]+graph[u][i]<dist[i]$时，置$dist[i]=dist[u]+graph[u][i]$，置$parent[i]=u$
• 一旦$S$包含了所有$V$中顶点，$dist$就记录了从源到所有其他顶点之间的最短路径长度

Dijkstra算法的正确性

贪心选择性质

• Dijkstra算法所做的贪心选择是从$V-S$中选择具有最短特殊路径的顶点$u$，从而确定从源到$u$的最短路径长度$dist[u]$，从源到$u$没有更短的其他路径
• 事实上，如果存在一条从源到$u$且长度比$dist[u]$更短的路，设这条路初次走出$S$之外到达的顶点为$x\in V-S$，然后徘徊于$S$内外若干次，最后离开$S$到达$u$

• 在这条路径上，分别记$d(v,x)$、$d(x,u)$和$d(v,u)$为顶点$v$到顶点$x$、顶点$x$到顶点$u$和顶点$v$到顶点$u$的路长，那么$dist[x]\le d(v,x)$，$d(v,x)+d(x,u)=d(v,u)<dist[u]$，利用边权的非负性，可知$d(x,u)\ge 0$，从而推得$dist[x]<dist[u]$，此为矛盾
• 这就证明了$dist[u]$是从源到顶点$u$的最短路径长度

最优子结构性质

• 将添加$u$之前的$S$称为$S^{{}^{\prime }}$
• 当添加了$u$后，可能出现一条到顶点$i$的新的特殊路

• 如果这条新特殊路是经过$S^{{}^{\prime }}$到达顶点$u$，然后从$u$经一条边直接到达顶点$i$，则这种路的最短的长度是$dist[u]+c[u][i]$，此时，如果$dist[u]+c[u][i]<dist[i]$，则算法中用$dist[u]+c[u][i]$作为$dist[i]$的新值
• 如果这条新特殊路经过$S^{{}^{\prime }}$到达$u$后，不是从$u$经一条边直接到达$i$，而是回到$S^{{}^{\prime }}$中某个顶点$x$，最后才到达顶点$i$，那么由于$x$在$S^{{}^{\prime }}$中，因此$x$比$u$先加入$S$，故从源到$x$的路的长度比从源到$u$，再从$u$到$x$的路的长度小，于是当前$dist[i]$的值小于这条新特殊路的长度，因此，在算法中不必考虑这种路
• 由此可知，不论算法中$dist[u]$的值是否有变化，它总是关于当前顶点集$S$到顶点$u$的最短特殊路径长度

Dijkstra算法应用示例

• 对下图中的有向图，应用Dijkstra算法计算从源顶点$1$到其他顶点间最短路径的过程如下表所示

Python实现

import sys


class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = []

    def printSolution(self, dist, parent):

        for v in range(self.V):
            path = []
            curr = v

            while curr != -1:
                path.append(curr)

                curr = parent[curr]

            path.reverse()

            print((v, dist[v], path))

    def minDistance(self, dist, sptSet):
        min_value = sys.maxsize
        min_index = -1

        for v in range(self.V):
            if not sptSet[v] and dist[v] < min_value:
                min_value = dist[v]
                min_index = v

        return min_index

    def dijkstra(self, src):
        dist = [sys.maxsize] * self.V
        dist[src] = 0

        sptSet = [False] * self.V

        parent = [-1] * self.V

        for _ in range(self.V):
            u = self.minDistance(dist, sptSet)

            sptSet[u] = True

            for v in range(self.V):
                if not sptSet[v] and self.graph[u][v] != 0 and 0 < dist[u] + self.graph[u][v] < dist[v]:
                    dist[v] = dist[u] + self.graph[u][v]
                    parent[v] = u

        self.printSolution(dist, parent)


g = Graph(9)

g.graph = [[0, 4, 0, 0, 0, 0, 0, 8, 0],
           [4, 0, 8, 0, 0, 0, 0, 11, 0],
           [0, 8, 0, 7, 0, 4, 0, 0, 2],
           [0, 0, 7, 0, 9, 14, 0, 0, 0],
           [0, 0, 0, 9, 0, 10, 0, 0, 0],
           [0, 0, 4, 14, 10, 0, 2, 0, 0],
           [0, 0, 0, 0, 0, 2, 0, 1, 6],
           [8, 11, 0, 0, 0, 0, 1, 0, 7],
           [0, 0, 2, 0, 0, 0, 6, 7, 0]]

src = 0

print('-' * 40)
print(f'(顶点, 以顶点 {src} 为源的最短路径长度, 最短路径)')
print('-' * 40)

g.dijkstra(src)

print('-' * 40)

----------------------------------------
(顶点, 以顶点 0 为源的最短路径长度, 最短路径)
----------------------------------------
(0, 0, [0])
(1, 4, [0, 1])
(2, 12, [0, 1, 2])
(3, 19, [0, 1, 2, 3])
(4, 21, [0, 7, 6, 5, 4])
(5, 11, [0, 7, 6, 5])
(6, 9, [0, 7, 6])
(7, 8, [0, 7])
(8, 14, [0, 1, 2, 8])
----------------------------------------

时间复杂性

• 对于一个具有$n$个顶点的带权有向图，Dijkstra算法进行二重循环，需要$O(n^2)$时间