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

文章目录

@[toc]
问题描述
`Dijkstra`算法
`Dijkstra`算法应用示例
时间复杂性
`Python`实现

个人主页：丷从心

系列专栏：贪心算法

问题描述

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

`Dijkstra`算法

Dijkstra算法是解单源最短路径问题的一个贪心算法
其基本思想是，设置顶点集合 $S$ ，并不断地做贪心选择来扩充这个集合，一个顶点属于集合 $S$ 当且仅当从源到该顶点地最短路径长度已知
初始时， $S$ 中仅含有源，设 $u$ 是 $G$ 的某一个顶点，把从源到 $u$ 且中间只经过 $S$ 中顶点的路称为从源到 $u$ 的特殊路径，并用数组 $d i s t$ 记录当前每个顶点所对应的最短特殊路径长度，用列表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算法计算从源顶点 $1$ 到其他顶点间最短路径的过程如下表所示

迭代	$S$	$u$	$d i s t [2]$	$d i s t [3]$	$d i s t [4]$	$d i s t [5]$
初始	$\set{1}$	$-$	$10$	$ma x in t$	$30$	$100$
$1$	$\set{1 , 2}$	$2$	$10$	$60$	$30$	$100$
$2$	$\set{1 , 2 , 3}$	$4$	$10$	$50$	$30$	$90$
$3$	$\set{1 , 2 , 4 , 3}$	$3$	$10$	$50$	$30$	$60$
$4$	$\set{1 , 2 , 4 , 3 , 5}$	$5$	$10$	$50$	$30$	$60$

时间复杂性

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

`Python`实现

import sys


class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0 for _ in range(vertices)] for _ in range(vertices)]

    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 dist[v] < min_value and not sptSet[v]:
                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 self.graph[u][v] != 0 and 0 < dist[u] + self.graph[u][v] < dist[v] and not sptSet[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(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])
----------------------------------------