Bellman Ford algoritması, ağırlıklı bir grafiğin bir tepe noktasından diğer tüm köşelerine en kısa yolu bulmamıza yardımcı olur.
Dijkstra'nın algoritmasına benzer, ancak kenarların negatif ağırlıklara sahip olabileceği grafiklerle çalışabilir.
Gerçek hayatta neden negatif ağırlıklı kenarlar olur?
Negatif ağırlık kenarları ilk bakışta işe yaramaz gibi görünebilir, ancak nakit akışı, kimyasal bir reaksiyonda açığa çıkan / emilen ısı vb.
Örneğin, bir kimyasal A'dan başka bir kimyasal B'ye ulaşmanın farklı yolları varsa, her yöntemin hem ısı yayılımını hem de soğurmayı içeren alt reaksiyonları olacaktır.
Minimum enerjinin gerekli olduğu reaksiyonlar kümesini bulmak istiyorsak, o zaman ısı emilimini negatif ağırlıklar ve ısı dağılımını pozitif ağırlıklar olarak hesaba katabilmemiz gerekir.
Negatif ağırlıklara neden dikkat etmemiz gerekiyor?
Negatif ağırlık kenarları, negatif ağırlık döngüleri, yani aynı noktaya geri gelerek toplam yol mesafesini azaltacak bir döngü oluşturabilir.
Negatif ağırlık döngüleri, en kısa yolu bulmaya çalışırken yanlış sonuç verebilir.
Dijkstra Algoritması gibi böyle bir döngüyü algılayamayan en kısa yol algoritmaları, negatif bir ağırlık döngüsünden geçip yol uzunluğunu azaltabildikleri için yanlış sonuç verebilir.
Bellman Ford'un algoritması nasıl çalışır?
Bellman Ford algoritması, başlangıç noktasından diğer tüm köşelere kadar olan yolun uzunluğunu fazla tahmin ederek çalışır. Ardından, önceden aşırı tahmin edilen yollardan daha kısa olan yeni yollar bularak bu tahminleri yinelemeli olarak gevşetir.
Bunu tüm köşeler için tekrar tekrar yaparak, sonucun optimize edilmesini garanti edebiliriz.
Bellman Ford algoritması için Adım-1 Bellman Ford algoritması için 
Adım-2 Bellman Ford algoritması için 
Adım-4 Bellman Ford algoritması için 
Adım-4 Bellman Ford algoritması için 
Adım-5 Bellman Ford algoritması için 
Adım-6
Bellman Ford Sözde Kodu
Her köşenin yol mesafesini korumalıyız. Bunu v boyutunda bir dizide saklayabiliriz, burada v köşe sayısıdır.
Sadece en kısa yolun uzunluğunu bilmekle kalmayıp, en kısa yolu da elde edebilmek istiyoruz. Bunun için, her bir tepe noktasını yol uzunluğunu en son güncelleyen tepe noktasına eşliyoruz.
Algoritma sona erdiğinde, yolu bulmak için hedef köşeden kaynak köşeye geri dönebiliriz.
fonksiyon bellmanFord (G, S) her köşe için G mesafe (V) <- sonsuz önceki (V) <- NULL mesafe (S) <- 0 her köşe için V her köşe için G'de (U, V) G'de tempDistance <- distance (U) + edge_weight (U, V) if tempDistance <distance (V) distance (V) <- tempDistance previous (V) <- U her kenar için (U, V) G olarak Mesafe (U) ise + edge_weight (U, V) <distance (V) Hata: Negatif Döngü Var dönüş mesafesi (), önceki ()
Bellman Ford ve Dijkstra
Bellman Ford'un algoritması ve Dijkstra'nın algoritması yapı olarak çok benzer. Dijkstra yalnızca bir tepe noktasının yakın komşularına bakarken, Bellman her yinelemede her kenardan geçiyor.
Dijkstra'nın Bellman Ford Algoritmasına Karşı
Python, Java ve C / C ++ Örnekleri
Python Java C C ++ # Bellman Ford Algorithm in Python class Graph: def __init__(self, vertices): self.V = vertices # Total number of vertices in the graph self.graph = () # Array of edges # Add edges def add_edge(self, s, d, w): self.graph.append((s, d, w)) # Print the solution def print_solution(self, dist): print("Vertex Distance from Source") for i in range(self.V): print("(0) (1)".format(i, dist(i))) def bellman_ford(self, src): # Step 1: fill the distance array and predecessor array dist = (float("Inf")) * self.V # Mark the source vertex dist(src) = 0 # Step 2: relax edges |V| - 1 times for _ in range(self.V - 1): for s, d, w in self.graph: if dist(s) != float("Inf") and dist(s) + w < dist(d): dist(d) = dist(s) + w # Step 3: detect negative cycle # if value changes then we have a negative cycle in the graph # and we cannot find the shortest distances for s, d, w in self.graph: if dist(s) != float("Inf") and dist(s) + w < dist(d): print("Graph contains negative weight cycle") return # No negative weight cycle found! # Print the distance and predecessor array self.print_solution(dist) g = Graph(5) g.add_edge(0, 1, 5) g.add_edge(0, 2, 4) g.add_edge(1, 3, 3) g.add_edge(2, 1, 6) g.add_edge(3, 2, 2) g.bellman_ford(0)
// Bellman Ford Algorithm in Java class CreateGraph ( // CreateGraph - it consists of edges class CreateEdge ( int s, d, w; CreateEdge() ( s = d = w = 0; ) ); int V, E; CreateEdge edge(); // Creates a graph with V vertices and E edges CreateGraph(int v, int e) ( V = v; E = e; edge = new CreateEdge(e); for (int i = 0; i < e; ++i) edge(i) = new CreateEdge(); ) void BellmanFord(CreateGraph graph, int s) ( int V = graph.V, E = graph.E; int dist() = new int(V); // Step 1: fill the distance array and predecessor array for (int i = 0; i < V; ++i) dist(i) = Integer.MAX_VALUE; // Mark the source vertex dist(s) = 0; // Step 2: relax edges |V| - 1 times for (int i = 1; i < V; ++i) ( for (int j = 0; j < E; ++j) ( // Get the edge data int u = graph.edge(j).s; int v = graph.edge(j).d; int w = graph.edge(j).w; if (dist(u) != Integer.MAX_VALUE && dist(u) + w < dist(v)) dist(v) = dist(u) + w; ) ) // Step 3: detect negative cycle // if value changes then we have a negative cycle in the graph // and we cannot find the shortest distances for (int j = 0; j < E; ++j) ( int u = graph.edge(j).s; int v = graph.edge(j).d; int w = graph.edge(j).w; if (dist(u) != Integer.MAX_VALUE && dist(u) + w < dist(v)) ( System.out.println("CreateGraph contains negative w cycle"); return; ) ) // No negative w cycle found! // Print the distance and predecessor array printSolution(dist, V); ) // Print the solution void printSolution(int dist(), int V) ( System.out.println("Vertex Distance from Source"); for (int i = 0; i 1 graph.edge(0).s = 0; graph.edge(0).d = 1; graph.edge(0).w = 5; // edge 0 --> 2 graph.edge(1).s = 0; graph.edge(1).d = 2; graph.edge(1).w = 4; // edge 1 --> 3 graph.edge(2).s = 1; graph.edge(2).d = 3; graph.edge(2).w = 3; // edge 2 --> 1 graph.edge(3).s = 2; graph.edge(3).d = 1; graph.edge(3).w = 6; // edge 3 --> 2 graph.edge(4).s = 3; graph.edge(4).d = 2; graph.edge(4).w = 2; graph.BellmanFord(graph, 0); // 0 is the source vertex ) )
// Bellman Ford Algorithm in C #include #include #define INFINITY 99999 //struct for the edges of the graph struct Edge ( int u; //start vertex of the edge int v; //end vertex of the edge int w; //weight of the edge (u,v) ); //Graph - it consists of edges struct Graph ( int V; //total number of vertices in the graph int E; //total number of edges in the graph struct Edge *edge; //array of edges ); void bellmanford(struct Graph *g, int source); void display(int arr(), int size); int main(void) ( //create graph struct Graph *g = (struct Graph *)malloc(sizeof(struct Graph)); g->V = 4; //total vertices g->E = 5; //total edges //array of edges for graph g->edge = (struct Edge *)malloc(g->E * sizeof(struct Edge)); //------- adding the edges of the graph /* edge(u, v) where u = start vertex of the edge (u,v) v = end vertex of the edge (u,v) w is the weight of the edge (u,v) */ //edge 0 --> 1 g->edge(0).u = 0; g->edge(0).v = 1; g->edge(0).w = 5; //edge 0 --> 2 g->edge(1).u = 0; g->edge(1).v = 2; g->edge(1).w = 4; //edge 1 --> 3 g->edge(2).u = 1; g->edge(2).v = 3; g->edge(2).w = 3; //edge 2 --> 1 g->edge(3).u = 2; g->edge(3).v = 1; g->edge(3).w = 6; //edge 3 --> 2 g->edge(4).u = 3; g->edge(4).v = 2; g->edge(4).w = 2; bellmanford(g, 0); //0 is the source vertex return 0; ) void bellmanford(struct Graph *g, int source) ( //variables int i, j, u, v, w; //total vertex in the graph g int tV = g->V; //total edge in the graph g int tE = g->E; //distance array //size equal to the number of vertices of the graph g int d(tV); //predecessor array //size equal to the number of vertices of the graph g int p(tV); //step 1: fill the distance array and predecessor array for (i = 0; i < tV; i++) ( d(i) = INFINITY; p(i) = 0; ) //mark the source vertex d(source) = 0; //step 2: relax edges |V| - 1 times for (i = 1; i <= tV - 1; i++) ( for (j = 0; j edge(j).u; v = g->edge(j).v; w = g->edge(j).w; if (d(u) != INFINITY && d(v)> d(u) + w) ( d(v) = d(u) + w; p(v) = u; ) ) ) //step 3: detect negative cycle //if value changes then we have a negative cycle in the graph //and we cannot find the shortest distances for (i = 0; i edge(i).u; v = g->edge(i).v; w = g->edge(i).w; if (d(u) != INFINITY && d(v)> d(u) + w) ( printf("Negative weight cycle detected!"); return; ) ) //No negative weight cycle found! //print the distance and predecessor array printf("Distance array: "); display(d, tV); printf("Predecessor array: "); display(p, tV); ) void display(int arr(), int size) ( int i; for (i = 0; i < size; i++) ( printf("%d ", arr(i)); ) printf(""); )
// Bellman Ford Algorithm in C++ #include // Struct for the edges of the graph struct Edge ( int u; //start vertex of the edge int v; //end vertex of the edge int w; //w of the edge (u,v) ); // Graph - it consists of edges struct Graph ( int V; // Total number of vertices in the graph int E; // Total number of edges in the graph struct Edge* edge; // Array of edges ); // Creates a graph with V vertices and E edges struct Graph* createGraph(int V, int E) ( struct Graph* graph = new Graph; graph->V = V; // Total Vertices graph->E = E; // Total edges // Array of edges for graph graph->edge = new Edge(E); return graph; ) // Printing the solution void printArr(int arr(), int size) ( int i; for (i = 0; i V; int E = graph->E; int dist(V); // Step 1: fill the distance array and predecessor array for (int i = 0; i < V; i++) dist(i) = INT_MAX; // Mark the source vertex dist(u) = 0; // Step 2: relax edges |V| - 1 times for (int i = 1; i <= V - 1; i++) ( for (int j = 0; j edge(j).u; int v = graph->edge(j).v; int w = graph->edge(j).w; if (dist(u) != INT_MAX && dist(u) + w < dist(v)) dist(v) = dist(u) + w; ) ) // Step 3: detect negative cycle // if value changes then we have a negative cycle in the graph // and we cannot find the shortest distances for (int i = 0; i edge(i).u; int v = graph->edge(i).v; int w = graph->edge(i).w; if (dist(u) != INT_MAX && dist(u) + w 1 graph->edge(0).u = 0; graph->edge(0).v = 1; graph->edge(0).w = 5; //edge 0 --> 2 graph->edge(1).u = 0; graph->edge(1).v = 2; graph->edge(1).w = 4; //edge 1 --> 3 graph->edge(2).u = 1; graph->edge(2).v = 3; graph->edge(2).w = 3; //edge 2 --> 1 graph->edge(3).u = 2; graph->edge(3).v = 1; graph->edge(3).w = 6; //edge 3 --> 2 graph->edge(4).u = 3; graph->edge(4).v = 2; graph->edge(4).w = 2; BellmanFord(graph, 0); //0 is the source vertex return 0; )
Bellman Ford'un Karmaşıklığı
Zaman Karmaşıklığı
| En İyi Durum Karmaşıklığı | O (E) |
| Ortalama Durum Karmaşıklığı | O (VE) |
| En Kötü Durum Karmaşıklığı | O (VE) |
Uzay Karmaşıklığı
Ve uzay karmaşıklığı O(V).
Bellman Ford'un Algoritma Uygulamaları
- Yönlendirme algoritmalarında en kısa yolları hesaplamak için
- En kısa yolu bulmak için
