--- Difficulty: Medium Source: 160 Days of Problem Solving Tags: - Graph - Dynamic Programming --- # πŸš€ _Day 16. Bellman-Ford_ 🧠 The problem can be found at the following link: [Question Link](https://www.geeksforgeeks.org/batch/gfg-160-problems/track/graph-gfg-160/problem/distance-from-the-source-bellman-ford-algorithm) ## πŸ’‘ **Problem Description:** Given a **weighted graph** with `V` vertices (numbered from `0` to `V-1`) and a list of `E` edges, where each edge is represented as a triplet `[u, v, w]` denoting a **directed edge from `u` to `v`** with weight `w`. Also given a source vertex `src`. Your task is to compute the **shortest distance from the source to all other vertices** using the **Bellman-Ford algorithm**. - If a vertex is unreachable from the source, mark its distance as **1e8**. - If the graph contains a **negative weight cycle**, return `[-1]`. > πŸ“ **Note:** Sorry for uploading late, my Final Sem exam is going on. ## πŸ” **Example Walkthrough:** ### **Example 1:** #### **Input:** ```text V = 5 edges = [[1, 3, 2], [4, 3, -1], [2, 4, 1], [1, 2, 1], [0, 1, 5]] src = 0 ``` #### **Output:** ```text [0, 5, 6, 6, 7] ``` #### **Explanation:** - 0 β†’ 1: 5 - 0 β†’ 1 β†’ 2: 6 - 0 β†’ 1 β†’ 2 β†’ 4 β†’ 3: 6 - 0 β†’ 1 β†’ 2 β†’ 4: 7 ### **Example 2:** #### **Input:** ```text V = 4 edges = [[0, 1, 4], [1, 2, -6], [2, 3, 5], [3, 1, -2]] src = 0 ``` #### **Output:** ```text [-1] ``` #### **Explanation:** - The cycle: 1 β†’ 2 β†’ 3 β†’ 1 has a negative weight β†’ **Negative Cycle Detected** ## **Constraints** - $\( 1 \leq V \leq 100 \)$ - $\( 1 \leq E = \text{edges.size()} \leq V \times (V-1) \)$ - $\( -1000 \leq w \leq 1000 \)$ - $\( 0 \leq \text{src} < V \)$ ## 🎯 **My Approach:** ### Standard Bellman-Ford Algorithm The Bellman-Ford algorithm is designed to find the shortest paths from a **single source** node to all other nodes, even when **negative edge weights** exist. ### **Algorithm Steps:** 1. Initialize a distance array `dist[]` of size `V` with all elements as `1e8`, and set `dist[src] = 0`. 2. Relax all edges `V - 1` times. 3. Check for negative weight cycles by attempting one more relaxation: - If any edge still updates, it means a negative cycle exists β†’ return `[-1]`. ## πŸ•’ **Time and Auxiliary Space Complexity** - **Expected Time Complexity:** $\( O(V \times E) \)$, as we perform edge relaxation `V-1` times over all `E` edges. - **Expected Auxiliary Space Complexity:** $\( O(V) \)$, to store the distance array of size `V`. ## πŸ“ **Solution Code** ## Code (C++) ```cpp // βœ… Standard Bellman-Ford Algorithm class Solution { public: vector bellmanFord(int V, vector>& edges, int src) { vector dist(V, 1e8); dist[src] = 0; for (int i = 0; i < V - 1; ++i) for (auto& e : edges) if (dist[e[0]] != 1e8 && dist[e[0]] + e[2] < dist[e[1]]) dist[e[1]] = dist[e[0]] + e[2]; for (auto& e : edges) if (dist[e[0]] != 1e8 && dist[e[0]] + e[2] < dist[e[1]]) return {-1}; return dist; } }; ```

⚑ Alternative Approaches

 ## πŸ“Š **2️⃣ Bellman-Ford with Early Termination Optimization** #### **Algorithm Steps:** 1. Initialize a distance array with a large value (here, `1e8`) and set the source distance to 0. 2. For each of the `V - 1` iterations, update the distances of the vertices. - If no update is made in an iteration, break out early to optimize runtime. 3. Check once more for any possible relaxation to detect negative cycles. 4. Return `{-1}` if a negative cycle is detected, else return the distance array. ```cpp class Solution { public: vector bellmanFord(int V, vector>& edges, int src) { vector dist(V, 1e8); dist[src] = 0; for (int i = 0; i < V - 1; ++i) { bool updated = false; for (auto& e : edges) { int u = e[0], v = e[1], w = e[2]; if (dist[u] != 1e8 && dist[u] + w < dist[v]) { dist[v] = dist[u] + w; updated = true; } } if (!updated) break; // Optimization } for (auto& e : edges) if (dist[e[0]] != 1e8 && dist[e[0]] + e[2] < dist[e[1]]) return {-1}; return dist; } }; ``` ### πŸ“ **Complexity Analysis** - **Time Complexity:** `O(V * E)` in worst-case, better with early break. - **Space Complexity:** `O(V)` ### βœ… **Why This?** This can significantly reduce computation when the graph stabilizes early. A practical tweak that saves time in sparse or nearly optimal graphs. ### πŸ†š Comparison of Approaches | **Approach** | ⏱️ **Time Complexity** | πŸ—‚οΈ **Space Complexity** | βœ… **Pros** | ⚠️ **Cons** | | ------------------------------------ | ------------------------------ | ----------------------- | ----------------------------------------- | --------------------------- | | **Standard Bellman-Ford** | 🟒 O(V Γ— E) | 🟒 O(V) | Simple, classic, handles all cases | May do redundant passes | | **Optimized with Early Termination** | 🟑 Best: O(E), Worst: O(V Γ— E) | 🟒 O(V) | Faster on converging graphs, fewer passes | Still worst-case `O(V Γ— E)` | - Use **Bellman-Ford** when negative weights or cycles are possible. - Use **Early Termination** for performance optimization.
## Code (Java) ```java class Solution { public int[] bellmanFord(int V, int[][] edges, int src) { int[] dist = new int[V]; Arrays.fill(dist, (int)1e8); dist[src] = 0; for (int i = 0; i < V - 1; i++) for (int[] e : edges) if (dist[e[0]] < 1e8 && dist[e[0]] + e[2] < dist[e[1]]) dist[e[1]] = dist[e[0]] + e[2]; for (int[] e : edges) if (dist[e[0]] < 1e8 && dist[e[0]] + e[2] < dist[e[1]]) return new int[]{-1}; return dist; } } ``` ## Code (Python) ```python class Solution: def bellmanFord(self, V, edges, src): dist = [int(1e8)] * V dist[src] = 0 for _ in range(V - 1): for u, v, w in edges: if dist[u] < 1e8 and dist[u] + w < dist[v]: dist[v] = dist[u] + w for u, v, w in edges: if dist[u] < 1e8 and dist[u] + w < dist[v]: return [-1] return dist ``` ## 🎯 **Contribution and Support:** For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: [Any Questions](https://www.linkedin.com/in/patel-hetkumar-sandipbhai-8b110525a/). Let’s make this learning journey more collaborative! ⭐ **If you find this helpful, please give this repository a star!** ⭐ ---

πŸ“Visitor Count