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

文章目录

• • @[toc]
  • • 问题描述
    • `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算法计算从源顶点$1$到其他顶点间最短路径的过程如下表所示

迭代	$S$	$u$	$dist[2]$	$dist[3]$	$dist[4]$	$dist[5]$
初始	{ ? 1 ? } \set{1} {1}	$?$	$10$	$maxint$	$30$	$100$
$1$	{ ? 1 , 2 ? } \set{1 , 2} {1,2}	$2$	$10$	$60$	$30$	$100$
$2$	{ ? 1 , 2 , 3 ? } \set{1 , 2 , 3} {1,2,3}	$4$	$10$	$50$	$30$	$90$
$3$	{ ? 1 , 2 , 4 , 3 ? } \set{1 , 2 , 4 , 3} {1,2,4,3}	$3$	$10$	$50$	$30$	$60$
$4$	{ ? 1 , 2 , 4 , 3 , 5 ? } \set{1 , 2 , 4 , 3 , 5} {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])
----------------------------------------

---