Python 中的 Dijkstra 演算法

Vaibhhav Khetarpal 2023年10月10日 Python

Dijkstra 演算法可以定義為一種貪婪演算法，可用於找出從源頂點到加權圖中存在的任何其他可能頂點的最短距離，前提是該頂點可從源頂點到達。

本教程討論在 Python 中實現尋找最短路徑的 Dijkstra 演算法。

如上所述，Dijkstra 的演算法是貪婪的。貪心演算法可以定義為一種演算法正規化，它專注於為給定問題構建一個逐個解決方案，然後選擇最有利的選項。

Dijkstra 演算法的工作原理如下。

給定幾個未訪問的頂點，選擇與源距離最小的頂點並訪問它。
然後更新每個鄰居的距離。對訪問頂點也是如此，它的當前距離大於它們之間給定邊的總和和權重。
需要重複步驟 1 和 2，直到沒有未訪問的頂點。

Dijkstra 演算法與另一種貪婪演算法 Prim 的最小生成樹演算法相似，因為它們都需要生成 SPT（最短路徑樹），以源為樹的根。

以下程式碼使用 Dijkstra 演算法在 Python 中尋找最短路徑。

import sys


class Graph:
    def __init__(self, vertx):
        self.V = vertx
        self.graph = [[0 for column in range(vertx)] for row in range(vertx)]

    def pSol(self, dist):
        print("Distance of vertex from source")
        for node in range(self.V):
            print(node, "t", dist[node])

    def minDistance(self, dist, sptSet):

        min = sys.maxsize

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

        return min_index

    def dijk(self, source):

        dist = [sys.maxsize] * self.V
        dist[source] = 0
        sptSet = [False] * self.V

        for cout 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 sptSet[v] == False
                    and dist[v] > dist[u] + self.graph[u][v]
                ):
                    dist[v] = dist[u] + self.graph[u][v]

        self.pSol(dist)


f = Graph(9)
f.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],
]

f.dijk(0)

上面的程式碼提供了以下輸出：

Distance of vertex from source
0 t 0
1 t 4
2 t 12
3 t 19
4 t 21
5 t 11
6 t 9
7 t 8
8 t 14

Dijkstra 的演算法與深度優先搜尋演算法非常相似，儘管這兩種演算法並非完全出於同一目的而存在。

深度優先搜尋和 Dijkstra 演算法之間唯一的顯著區別是前者的工作速度比後者慢，因為深度優先搜尋 (DFS) 演算法使用堆疊技術。另一方面，Dijkstra 的演算法利用了相對較慢的堆技術。

Enjoying our tutorials? Subscribe to DelftStack on YouTube to support us in creating more high-quality video guides. Subscribe

作者： Vaibhhav Khetarpal

Vaibhhav is an IT professional who has a strong-hold in Python programming and various projects under his belt. He has an eagerness to discover new things and is a quick learner.