feat: implement Bellman Ford algorithm

ceeninja · ceeninja · commit 7e2ee4965e0e · 2021-10-27T10:12:14.000+02:00
diff --git a/Programs/BellmanFord.java b/Programs/BellmanFord.java
@@ -0,0 +1,107 @@
+// 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 < V; ++i)
+      System.out.println(i + "\t\t" + dist[i]);
+  }
+
+  public static void main(String[] args) {
+    int V = 5; // Total vertices
+    int E = 8; // Total Edges
+
+    CreateGraph graph = new CreateGraph(V, E);
+
+    // edge 0 --> 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
+  }
+}
