Bellman-Ford Algorithm — Algorithm Visualization & Coding Challenge
Choose Your Learning Path
How would you like to learn today?
Visualize algorithms in real time, explore them step by step, or challenge yourself with a test.Choose a path to focus—or scroll down to preview all options.
🧠 Active Learning
Visualize the algorithm step-by-step with interactive animations in real time.
📖 Passive Learning
Read the full explanation, examples, and starter code at your own pace.
🎯 Challenge Mode
Drag and arrange the algorithm steps in the correct execution order.
🧠 Select Active to activate
Watch algorithms run step by step.
Follow every state change, comparison, and transformation as the execution unfolds in real time.
📖 Select Passive to activate
Understanding Bellman-Ford Algorithm
Detailed explanation and reference materialsProblem Overview
Bellman-Ford Algorithm
The Bellman-Ford Algorithm is a graph algorithm used to find the shortest path from a single source vertex to all other vertices in a weighted graph. It is particularly useful when the graph contains negative weight edges.
Algorithm Steps
- Initialize distances:
- Set the distance to the source vertex as
0and all other vertices as∞(infinity).
- Set the distance to the source vertex as
- Relax edges (V - 1) times:
- Iterate over all edges and update the distance to each vertex if a shorter path is found.
- Check for negative-weight cycles:
- Run one more iteration over all edges.
- If any distance can still be reduced, the graph contains a negative-weight cycle.
Complexity Analysis
Time Complexity:
- The algorithm runs (V - 1) iterations, where each iteration processes E edges.
- This results in a time complexity of O(VE), making it slower than Dijkstra's algorithm for dense graphs.
Space Complexity:
- The algorithm requires an array to store distances, leading to a space complexity of O(V).
Applications
Detecting Negative-Weight Cycles
The Bellman-Ford algorithm can detect negative-weight cycles, which are cycles in a graph where the sum of edge weights is negative. If such a cycle exists, the algorithm reports it, preventing incorrect shortest path calculations.
Shortest Path Calculation
Bellman-Ford is useful for finding the shortest path in graphs that contain negative-weight edges, unlike Dijkstra’s algorithm, which fails with negative weights.
Routing Protocols
The algorithm is used in network routing protocols such as RIP (Routing Information Protocol) to find the shortest paths in a network.
Example Graph
Consider the following weighted directed graph:
A --(4)--> B
A --(1)--> C
B --(-2)--> C
C --(2)--> D
If A is the source vertex, the Bellman-Ford algorithm computes the shortest paths from A to all other vertices, considering both positive and negative edge weights.
OUTPUT: Shortest distances from source 0: To vertex 0 is 0 To vertex 1 is 6 To vertex 2 is 7 To vertex 3 is 2 To vertex 4 is 4
— Written by Saurabh Patil • B.Tech CSE • Software DeveloperStarter Code
🎯 Select Challenge to activate
Think & Arrange, Don't Just Copy-Paste
Drag and arrange the algorithm steps in the correct execution order instead of spending time typing code letter by letter.
Arrange the Algorithm Correctly 🧩
The algorithm is divided into three logical parts. Carefully rearrange each section in the correct order to form a complete and valid solution.
Understand Below AlgorithmOR
Don't Know Current Algorithm ?
Green text means the instruction is placed in the correct position.
Red text means the instruction is in the wrong position.
Instructions with the same background color indicate particular blocks start and end.
A tick mark means the instruction is correct and locked.
🔒 Locked steps cannot be moved. Only unlocked steps are draggable.
🔊 Enable sound for swap feedback and completion effects.