Bellman-Ford Algoritması

Bellman Ford Algoritmasının amacı bir şekil üzerindeki, başlangıç node’udan hedefe giden en kısa yolu bulmaktır. Bu sebeple Shortest path algorithm olarak sınıflandırılır.

Bellman Ford Algoritması ağırlıklı şekiller (weighted graph) üzerinde çalışır. Ggrafın negatif uzunlukta bir loop içermemesi koşuluyla her türlü grafı işleyebilir. Dijkstra algoritmasına göre performansı düşük olsada graftaki ağırlıkların eksi(-) olması durumunda Dijkstra’nın aksine başarılı çalışır.

D(i) ==[D1(i) …. DN(i)] ve S(i) =[S1(i) …. SN(i)]
D (i) : Düğüm i nin ağ daki diğer düğümler ile arasındaki minimun gecikmenin hesabı
S(i) : Her hedef düğüm için en iyi bağlantı yaptığı düğüm
N : Ağdaki düğümlerin numaraları
k : Kaynağa direkt bağlı veya en fazla 1 atlatmayla ulaşılabilecek düğümlerin kümesi

Step 0

Step 1

B=AB , min(A,B)= 0-> 0+2 = 2

D=AD , min(A,D)= 0-> 0+3 = 3

Step 2

C=BC , min(B,C)= 2-> 2–4 = -2

Step 3

E=DE , min(D,E)= 3-> 3+2 = 5

E=BE , min(D,E)= 2-> 2+1 = 3

E=CE , min(D,E)= -2-> -2+7 = 5

E = 3

Step 4

F=DF , min(D,F)= 3-> 3–2 = 1

F=EF , min(E,F)= 3-> 3+5 = 8

F = 1

Sonuç olarak;

#include <bits/stdc++.h>
struct Edge {
   int src, dest, weight;
};
struct Graph {
   int V, E;
   struct Edge* edge;
};
struct Graph* createGraph(int V, int E) {
   struct Graph* graph = new Graph;
   graph->V = V;
   graph->E = E;
   graph->edge = new Edge[E];
   return graph;
}
void BellmanFord(struct Graph* graph, int src) {
   int V = graph->V;
   int E = graph->E;
   int dist[V];
   for (int i = 0; i < V; i++)
      dist[i] = INT_MAX;
      dist[src] = 0;
   for (int i = 1; i <= V - 1; i++) {
      for (int j = 0; j < E; j++) {
         int u = graph->edge[j].src;
         int v = graph->edge[j].dest;
         int weight = graph->edge[j].weight;
         if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
         dist[v] = dist[u] + weight;
      }
   }
   for (int i = 0; i < E; i++) {
      int u = graph->edge[i].src;
      int v = graph->edge[i].dest;
      int weight = graph->edge[i].weight;
      if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
         printf("Graph contains negative weight cycle");
         return;
      }
   }
   printf("Vertex :\t\t    ");
   for (int i = 0; i < V; ++i)
      printf("%d \t", i);
      printf("\nDistance (from the source): ");
   for (int i = 0; i < V; ++i)
      printf("%d \t",dist[i]);
   return;
}


int main() {
   int V = 6;
   int E = 8;
   struct Graph* graph = createGraph(V, E);
   graph->edge[0].src = 0;
   graph->edge[0].dest = 3;
   graph->edge[0].weight = 3;
   graph->edge[1].src = 0;
   graph->edge[1].dest = 1;
   graph->edge[1].weight = 2;
   graph->edge[2].src = 1;
   graph->edge[2].dest = 2;
   graph->edge[2].weight =-4;
   graph->edge[3].src = 3;
   graph->edge[3].dest = 4;
   graph->edge[3].weight = 2;
   graph->edge[4].src = 1;
   graph->edge[4].dest = 4;
   graph->edge[4].weight = 1;
   graph->edge[5].src = 2;
   graph->edge[5].dest = 4;
   graph->edge[5].weight = 7;
   graph->edge[6].src = 3;
   graph->edge[6].dest = 5;
   graph->edge[6].weight = -2;
   graph->edge[7].src = 4;
   graph->edge[7].dest = 5;
   graph->edge[7].weight = 5;  
   BellmanFord(graph, 0);
   return 0;
}

Kaynak : https://www.tutorialspoint.com/bellman-ford-algorithm-in-cplusplus