Bagaimana untuk menulis algoritma Bellman-Ford dalam Python?

Bagaimana cara menulis algoritma Bellman-Ford dalam Python?

Algoritma Bellman-Ford ialah algoritma untuk menyelesaikan masalah laluan terpendek satu sumber dengan tepi berat negatif. Artikel ini akan memperkenalkan cara menggunakan Python untuk menulis algoritma Bellman-Ford dan memberikan contoh kod khusus.

Idea teras algoritma Bellman-Ford adalah untuk mengoptimumkan laluan melalui lelaran langkah demi langkah sehingga laluan terpendek ditemui. Langkah-langkah algoritma adalah seperti berikut:

1. Buat dist tatasusunan[] untuk menyimpan jarak terpendek dari titik sumber ke bucu lain.
2. Mulakan semua elemen tatasusunan dist[] kepada infiniti, tetapi dengan jarak 0 dari titik sumber.
3. Melalui lelaran n-1, untuk setiap tepi (u, v):
   1) Jika dist[v] > dist[u] + weight(u, v), kemas kini dist[v] kepada dist[ u] + berat (u, v).
4. Periksa sama ada terdapat kitaran berat negatif. Untuk setiap tepi (u, v):
   1) Jika dist[v] > dist[u] + weight(u, v), terdapat kitaran berat negatif dan laluan terpendek tidak dapat ditentukan.
5. Jika tiada kitaran berat negatif, laluan terpendek telah dikira dan tatasusunan dist[] ialah laluan terpendek.

Berikut ialah contoh kod algoritma Bellman-Ford yang ditulis dalam Python:

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

    def add_edge(self, u, v, w):
        self.graph.append([u, v, w])

    def bellman_ford(self, src):
        dist = [float("Inf")] * self.V
        dist[src] = 0

        for _ in range(self.V - 1):
            for u, v, w in self.graph:
                if dist[u] != float("Inf") and dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w

        for u, v, w in self.graph:
            if dist[u] != float("Inf") and dist[u] + w < dist[v]:
                print("图中存在负权环，无法确定最短路径")
                return

        self.print_solution(dist)

    def print_solution(self, dist):
        print("顶点    最短距离")
        for i in range(self.V):
            print(i, "        ", dist[i])

# 示例用法
g = Graph(5)
g.add_edge(0, 1, -1)
g.add_edge(0, 2, 4)
g.add_edge(1, 2, 3)
g.add_edge(1, 3, 2)
g.add_edge(1, 4, 2)
g.add_edge(3, 2, 5)
g.add_edge(3, 1, 1)
g.add_edge(4, 3, -3)
g.bellman_ford(0)

Dalam contoh di atas, graf g dicipta dan beberapa tepi ditambah. Kemudian panggil kaedah bellman_ford untuk mengira laluan terpendek dan mencetak hasilnya. Dalam contoh ini, titik sumber ialah 0 dan laluan terpendek akan dikira.

Kerumitan masa bagi algoritma Bellman-Ford ialah O(V*E), dengan V ialah bilangan bucu dan E ialah bilangan tepi. Dalam aplikasi praktikal, jika terdapat kitaran berat negatif dalam graf, algoritma tidak akan berhenti tetapi akan memasuki gelung tak terhingga. Oleh itu, apabila menggunakan algoritma Bellman-Ford, anda harus terlebih dahulu menyemak sama ada terdapat kitaran berat negatif.

Atas ialah kandungan terperinci Bagaimana untuk menulis algoritma Bellman-Ford dalam Python?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!