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

2023-12-23 21:49:26

个人主页:丷从心

系列专栏:贪心算法

从心


问题描述

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

Dijkstra算法

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

Dijkstra算法应用示例

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

1

迭代 S S S u u u d i s t [ 2 ] dist[2] dist[2] d i s t [ 3 ] dist[3] dist[3] d i s t [ 4 ] dist[4] dist[4] d i s t [ 5 ] dist[5] dist[5]
初始 { ? 1 ? } \set{1} {1} ? - ? 10 10 10 m a x i n t maxint maxint 30 30 30 100 100 100
1 1 1 { ? 1 , 2 ? } \set{1 , 2} {1,2} 2 2 2 10 10 10 60 60 60 30 30 30 100 100 100
2 2 2 { ? 1 , 2 , 3 ? } \set{1 , 2 , 3} {1,2,3} 4 4 4 10 10 10 50 50 50 30 30 30 90 90 90
3 3 3 { ? 1 , 2 , 4 , 3 ? } \set{1 , 2 , 4 , 3} {1,2,4,3} 3 3 3 10 10 10 50 50 50 30 30 30 60 60 60
4 4 4 { ? 1 , 2 , 4 , 3 , 5 ? } \set{1 , 2 , 4 , 3 , 5} {1,2,4,3,5} 5 5 5 10 10 10 50 50 50 30 30 30 60 60 60

时间复杂性

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

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])
----------------------------------------

文章来源:https://blog.csdn.net/from__2023_11_28/article/details/135174447
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。