Geekly articles weekly

Algoritma Bellman-Ford

Untuk mengantisipasi dimulainya kursus "Algoritma untuk Pengembang", mereka menyiapkan terjemahan lain dari artikel yang menarik.



Masalah : Diberikan grafik dan simpul awal src dalam grafik, perlu menemukan jalur terpendek dari src ke semua simpul dalam grafik yang diberikan. Grafik mungkin berisi sisi-sisi dengan bobot negatif.

Kami telah membahas algoritma Dijkstra sebagai cara untuk menyelesaikan masalah ini. Algoritma Dijkstra adalah algoritma serakah, dan kompleksitasnya adalah O (VLogV) (menggunakan tumpukan Fibonacci). Namun, Dijkstra tidak berfungsi untuk grafik dengan bobot tepi negatif, sementara Bellman-Ford sepenuhnya. Algoritma Bellman-Ford bahkan lebih sederhana daripada algoritma Dijkstra, dan sangat cocok untuk sistem terdistribusi. Pada saat yang sama, kompleksitasnya adalah O (VE) , yang lebih dari sekadar indikator untuk algoritma Dijkstra.

Rekomendasi : Sebelum beralih ke melihat solusi, cobalah berlatih sendiri.

Algoritma


Berikut ini adalah langkah-langkah terperinci.

Input : Grafik dan vertex awal src .
Output : Jarak terdekat ke semua simpul dari src. Jika siklus bobot negatif terjadi, maka jarak terdekat tidak dihitung, sebuah pesan ditampilkan yang menunjukkan adanya siklus semacam itu.

  1. Pada langkah ini, jarak dari titik awal ke semua titik lainnya diinisialisasi sebagai tak terbatas, dan jarak ke src itu sendiri diasumsikan 0. Jarak array dist[] ukuran |V| dengan semua nilai sama dengan tak terhingga, dengan pengecualian elemen dist[src] , di mana src adalah simpul asli.
  2. Langkah kedua menghitung jarak terpendek. Langkah-langkah berikut harus dilakukan |V| -1 kali, di mana |V| - jumlah simpul dalam grafik ini.
    • Lakukan tindakan berikut untuk setiap tepi uv :
      Jika dist[v] > dist[u] + uv , maka perbarui dist[v]
      dist [v] = dist [u] + uv
  3. Pada langkah ini, dilaporkan apakah ada siklus bobot negatif dalam grafik. Untuk setiap tepi uv , lakukan hal berikut:

    • Jika dist[v] > dist[u] + uv , maka grafik berisi siklus bobot negatif.

Gagasan langkah 3 adalah langkah 2 menjamin jarak terpendek jika grafik tidak mengandung siklus bobot negatif. Jika kita memeriksa semua sisi lagi dan mendapatkan lintasan yang lebih pendek untuk setiap simpul, ini akan menjadi sinyal keberadaan siklus bobot negatif.

Bagaimana cara kerjanya? Seperti dalam tugas pemrograman dinamis lainnya, algoritma menghitung jalur terpendek dari bawah ke atas. Pertama, ia menghitung jarak terpendek, yaitu jalur dengan panjang tidak lebih dari satu sisi. Kemudian ia menghitung jalur terpendek dengan panjang tidak lebih dari dua sisi dan seterusnya. Setelah iterasi loop luar, jalur terpendek dengan panjang tidak lebih dari i tepi dihitung. Dalam lintasan sederhana apa pun, bisa ada batas maksimum | V | -1 , sehingga loop luar berjalan tepat | V | -1 kali. Idenya adalah bahwa jika kita menghitung jalur terpendek dengan tidak lebih dari i edge, maka iterasi semua tepi menjamin mendapatkan jalur terpendek dengan tidak lebih dari i +1 edge (buktinya cukup sederhana, Anda dapat merujuk kuliah ini atau kuliah video dari MIT )

Contoh


Mari kita lihat algoritma pada contoh grafik berikut. Gambar diambil dari sini .
Biarkan titik awal menjadi 0. Ambil semua jarak sebagai tak terbatas, kecuali jarak ke src itu sendiri. Jumlah total simpul dalam grafik adalah 5, jadi semua ujungnya harus 4 kali.



Biarkan tulang iga dikerjakan dengan urutan sebagai berikut: (B, E), (D, B), (B, D), (A, B), (A, C), (D, C), (B, C), ( E, D). Kami mendapatkan jarak berikut ketika bagian di sepanjang tulang rusuk selesai untuk pertama kalinya. Baris pertama menunjukkan jarak awal, baris kedua menunjukkan jarak ketika tepi (B, E), (D, B), (B, D) dan (A, B) diproses. Baris ketiga menunjukkan jarak pemrosesan (A, C). Baris keempat menunjukkan apa yang terjadi ketika (D, C), (B, C) dan (E, D) diproses.



Iterasi pertama memastikan bahwa semua jalur terpendek tidak lebih dari jalur 1 tepi. Kami mendapatkan jarak berikut ketika lintasan kedua di semua tepi selesai (baris terakhir menunjukkan nilai akhir).



Iterasi kedua memastikan bahwa semua jalur terpendek memiliki panjang paling banyak 2 sisi. Algoritme berjalan sepanjang semua tepi 2 kali lebih banyak. Jarak diminimalkan setelah iterasi kedua, sehingga iterasi ketiga dan keempat tidak memperbarui nilai jarak.

Implementasi:

 # Python program for Bellman-Ford's single source # shortest path algorithm. from collections import defaultdict # Class to represent a graph class Graph: def __init__(self, vertices): self.V = vertices # No. of vertices self.graph = [] # default dictionary to store graph # function to add an edge to graph def addEdge(self, u, v, w): self.graph.append([u, v, w]) # utility function used to print the solution def printArr(self, dist): print("Vertex Distance from Source") for i in range(self.V): print("% d \t\t % d" % (i, dist[i])) # The main function that finds shortest distances from src to # all other vertices using Bellman-Ford algorithm. The function # also detects negative weight cycle def BellmanFord(self, src): # Step 1: Initialize distances from src to all other vertices # as INFINITE dist = [float("Inf")] * self.V dist[src] = 0 # Step 2: Relax all edges |V| - 1 times. A simple shortest # path from src to any other vertex can have at-most |V| - 1 # edges for i in range(self.V - 1): # Update dist value and parent index of the adjacent vertices of # the picked vertex. Consider only those vertices which are still in # queue for u, v, w in self.graph: if dist[u] != float("Inf") and dist[u] + w < dist[v]: dist[v] = dist[u] + w # Step 3: check for negative-weight cycles. The above step # guarantees shortest distances if graph doesn't contain # negative weight cycle. If we get a shorter path, then there # is a cycle. for u, v, w in self.graph: if dist[u] != float("Inf") and dist[u] + w < dist[v]: print "Graph contains negative weight cycle" return # print all distance self.printArr(dist) g = Graph(5) g.addEdge(0, 1, -1) g.addEdge(0, 2, 4) g.addEdge(1, 2, 3) g.addEdge(1, 3, 2) g.addEdge(1, 4, 2) g.addEdge(3, 2, 5) g.addEdge(3, 1, 1) g.addEdge(4, 3, -3) # Print the solution g.BellmanFord(0) # This code is contributed by Neelam Yadav


Nilai Output:



Catatan:

  1. Bobot negatif ditemukan dalam berbagai aplikasi grafik. Misalnya, alih-alih meningkatkan biaya jalur, kita dapat mengambil manfaat dengan mengikuti jalur tertentu.
  2. Algoritma Bellman-Ford bekerja lebih baik untuk sistem terdistribusi (lebih baik daripada algoritma Dijkstra). Tidak seperti Dijkstra, di mana kita perlu menemukan nilai minimum dari semua simpul, di Bellman Ford, edge dianggap satu per satu.

Latihan:

  1. Algoritma Bellman-Ford standar melaporkan jalur terpendek hanya jika tidak memiliki siklus bobot negatif. Modifikasi sehingga melaporkan jalur terpendek bahkan jika ada siklus seperti itu.
  2. Bisakah kita menggunakan algoritma Dijkstra untuk menemukan jalur terpendek dalam grafik dengan bobot negatif? Ada ide seperti itu: hitung nilai bobot minimum, tambahkan nilai positif (sama dengan nilai absolut dari nilai bobot minimum) ke semua bobot dan jalankan algoritma Dijkstra untuk grafik yang dimodifikasi. Akankah algoritma seperti itu bekerja?

Implementasi sederhana dari algoritma Bellman-Ford

Sumber:

www.youtube.com/watch?v=Ttezuzs39nk
en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm
www.cs.arizona.edu/classes/cs445/spring07/ShortestPath2.prn.pdf

Source: https://habr.com/ru/post/id484382/

More articles:


All Articles