DSA Notes
HubAlgorithm vs Data Structure - Key DifferencesReal-World Applications of DSATime and Space Complexity OverviewWhat is DSA? Data Structures and AlgorithmsWhy Learn Data Structures and AlgorithmsAsymptotic Analysis - Understanding Algorithm GrowthBest, Average, and Worst Case AnalysisBig O Notation - Upper Bound AnalysisBig Omega Notation - Lower Bound AnalysisBig Theta Notation - Tight Bound AnalysisSpace Complexity - Memory AnalysisTime Complexity Examples and AnalysisArray Interview Problems and SolutionsArray Operations - Insert, Delete, SearchArray Rotation TechniquesArray Searching TechniquesArrays - Fundamental Data StructureDynamic Arrays - Flexible SizingMultidimensional Arrays - 2D and BeyondSliding Window Technique for ArraysAnagram Problems - Character RearrangementPalindrome Problems and SolutionsPattern Searching in StringsString Interview Problems CollectionString Matching Algorithms - Pattern SearchingString Operations - Concatenation, Substring, ManipulationString Data Structure - FundamentalsCircular Linked List - Ring StructureDoubly Linked List - Bidirectional TraversalLinked List Interview ProblemsLinked List - Data Structure FundamentalsLinked List Operations - Insert, Delete, ReverseReverse Linked List - Iterative and RecursiveSingly Linked List - Implementation and OperationsBalanced Parentheses - Stack ApplicationInfix, Prefix, Postfix Expressions - Stack ApplicationStack Implementation TechniquesStack Interview Problems and SolutionsStack Data Structure - LIFO PrincipleStack using Arrays - Static ImplementationStack using Linked Lists - Dynamic ImplementationCircular Queue - Efficient Space UsageDeque (Double Ended Queue)Priority Queue - Custom OrderingQueue Applications - Real-World Use CasesQueue Implementation - Array and Linked ListQueue Interview Problems and SolutionsQueue Data Structure - FIFO PrincipleAVL Tree - Self-Balancing Binary Search TreeBinary Search Tree (BST)Binary Tree - Structure and OperationsFenwick Tree (Binary Indexed Tree)Red-Black Tree - Another Balanced BSTSegment Tree - Range Query Data StructureTree Interview Problems CollectionTree Data Structure FundamentalsTree Traversals - Inorder, Preorder, Postorder, Level OrderHeap Data StructureHeap OperationsHeap Interview ProblemsMax-HeapMin-Heap Implementation and Use CasesPriority Queue using HeapBellman-Ford AlgorithmBreadth-First Search (BFS) AlgorithmDepth-First Search (DFS) AlgorithmDijkstra\Floyd-Warshall AlgorithmGraph Interview ProblemsGraph Data Structure FundamentalsGraph Representation MethodsKruskal\Minimum Spanning Tree (MST)Prim\Shortest Path Algorithms: Complete ComparisonTopological SortingUnion-Find (Disjoint Set Union)Separate ChainingCollision HandlingHash FunctionsHashing FundamentalsHashing Interview ProblemsOpen AddressingBubble Sort - Simple Sorting AlgorithmCounting Sort - Non-Comparison SortingHeap Sort - Heap Based SortingInsertion Sort - Build Sorted ArrayMerge Sort - Divide and ConquerQuick Sort - Partition Based SortingRadix Sort - Digit Based SortingSelection Sort - Selection Based SortingSorting Algorithms Comparison - Choosing the Right AlgorithmSorting Algorithms - Fundamentals and ConceptsBinary Search - Efficient SearchingInterpolation Search - Intelligent SearchingLinear Search - Sequential Search AlgorithmSearch Algorithms ComparisonSearching Algorithm Interview ProblemsTernary Search AlgorithmBacktracking with RecursionRecursion Fundamentals - Base Case and RecurrenceRecursion Problems and SolutionsRecursion Tree - Visualizing Function CallsRecursion vs Iteration - Comparing ApproachesTail Recursion - Optimization TechniqueDynamic Programming Interview ProblemsDynamic Programming FundamentalsFibonacci with Dynamic Programming0/1 Knapsack ProblemLongest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Matrix Chain MultiplicationMemoization (Top-Down Dynamic Programming)Tabulation (Bottom-Up Dynamic Programming)Activity Selection ProblemFractional KnapsackGreedy Interview ProblemsGreedy Algorithm FundamentalsHuffman Coding — Data Structures & AlgorithmsJob Sequencing with DeadlinesBacktracking FundamentalsBacktracking Practice ProblemsN-Queens ProblemRat in a MazeSubset GenerationSudoku SolverCodeforces Guide for Competitive ProgrammersCommon Competitive Programming TechniquesContest Strategies for Competitive ProgrammingCompetitive Programming IntroductionFast Input/Output for Competitive ProgrammingLeetCode Guide for Interview PreparationBit Manipulation - Advanced TechniquesBloom Filter - Probabilistic Data StructureComputational Geometry - Algorithms and TechniquesDisjoint Set Union (DSU) - Union FindRandomized Algorithms - Probabilistic ComputingSkip List - Probabilistic Balanced StructureSuffix Array - String IndexingTrie - Prefix Tree for Efficient SearchingAutocomplete System Using TrieLibrary Management System Using DSARoute Finder Using GraphsMini Search Engine ProjectSocial Network Analysis Using GraphsEssential Coding Patterns for InterviewsDSA Cheatsheet: Quick ReferenceEssential DSA Interview QuestionsFAANG DSA Sheet: Company-Specific Patterns and ProblemsProblem Solving Strategies for Coding InterviewsComplexity CheatsheetImportant Algorithms SummaryBest Practice Platforms for DSARecommended Books for DSA
Learn Bellman-Ford shortest path algorithm that handles negative edge weights, detects negative cycles, with complete implementation and analysis.
Why Bellman-Ford?
Dijkstra's algorithm fails when graphs have negative edge weights. Consider a graph where going through a negative-weight edge actually makes a path shorter — Dijkstra's greedy approach would miss this because it finalizes vertices too early. Bellman-Ford solves this by taking a more patient approach: relax ALL edges, not just once, but V-1 times.
The Core Idea
The algorithm is beautifully simple:
- Relax every edge in the graph V-1 times
- After V-1 iterations, all shortest paths are guaranteed to be found
- If a V-th iteration still improves any distance, a negative cycle exists
Why V-1? Because the shortest path between any two vertices has at most V-1 edges (it visits each vertex at most once). Each iteration of relaxation fixes the shortest path for paths with one more edge. So after V-1 iterations, all paths of length up to V-1 are optimal.
Algorithm Steps
Example
1. Initialize: dist[source] = 0, dist[all others] = infinity
2. Repeat V-1 times:
For each edge (u, v, weight):
If dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight
3. Check for negative cycles:
For each edge (u, v, weight):
If dist[u] + weight < dist[v]:
Negative cycle exists!
Step-by-Step Example
Graph (directed)
A --(-1)--> B --(3)--> C
| ^
+--(4)---> D --(-2)-->+
Edges: (A,B,-1), (A,D,4), (B,C,3), (D,C,-2)
Source: A, Vertices = 4, so we do 3 iterations
Initial: dist = {A:0, B:inf, C:inf, D:inf}
Iteration 1 (relax all edges)
(A,B,-1): dist[A]+(-1) = -1 < inf → dist[B] = -1
(A,D,4): dist[A]+4 = 4 < inf → dist[D] = 4
(B,C,3): dist[B]+3 = 2 < inf → dist[C] = 2
(D,C,-2): dist[D]+(-2) = 2 = 2 → no change
dist = {A:0, B:-1, C:2, D:4}
Iteration 2
(A,B,-1): 0+(-1)=-1 = -1 → no change
(A,D,4): 0+4=4 = 4 → no change
(B,C,3): -1+3=2 = 2 → no change
(D,C,-2): 4+(-2)=2 = 2 → no change
No changes — algorithm converged early!
Iteration 3: No changes.
Negative cycle check: No edge improves. Safe!
Final: dist = {A:0, B:-1, C:2, D:4}
Python Implementation
Example
def bellman_ford(vertices, edges, source):
"""
vertices: list of vertex labels
edges: list of (u, v, weight) tuples
source: starting vertex
Returns: (distances dict, predecessors dict) or raises if negative cycle
"""
dist = {v: float('inf') for v in vertices}
prev = {v: None for v in vertices}
dist[source] = 0
# Relax all edges V-1 times
for i in range(len(vertices) - 1):
updated = False
for u, v, weight in edges:
if dist[u] != float('inf') and dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight
prev[v] = u
updated = True
# Early termination optimization
if not updated:
break
# Check for negative cycles
for u, v, weight in edges:
if dist[u] != float('inf') and dist[u] + weight < dist[v]:
raise ValueError("Graph contains a negative-weight cycle")
return dist, prev
# Example usage
vertices = ['A', 'B', 'C', 'D']
edges = [('A','B',-1), ('A','D',4), ('B','C',3), ('D','C',-2)]
dist, prev = bellman_ford(vertices, edges, 'A')
print(dist) # {'A': 0, 'B': -1, 'C': 2, 'D': 4}
C++ Implementation
Example
#include <vector>
#include <climits>
using namespace std;
struct Edge {
int u, v, weight;
};
vector<int> bellmanFord(int V, vector<Edge>& edges, int source) {
vector<int> dist(V, INT_MAX);
dist[source] = 0;
// Relax all edges V-1 times
for (int i = 0; i < V - 1; i++) {
bool updated = false;
for (auto& e : edges) {
if (dist[e.u] != INT_MAX && dist[e.u] + e.weight < dist[e.v]) {
dist[e.v] = dist[e.u] + e.weight;
updated = true;
}
}
if (!updated) break;
}
// Negative cycle detection
for (auto& e : edges) {
if (dist[e.u] != INT_MAX && dist[e.u] + e.weight < dist[e.v]) {
// Negative cycle exists
return {};
}
}
return dist;
}
Time and Space Complexity
- Time: O(V × E) — V-1 iterations, each processing all E edges
- Space: O(V) — for distance and predecessor arrays
- Slower than Dijkstra O((V+E) log V) but handles negative weights
Bellman-Ford vs Dijkstra
| Feature | Dijkstra | Bellman-Ford |
|---|---|---|
| Negative weights | Cannot handle | Handles correctly |
| Negative cycle detection | No | Yes |
| Time complexity | O((V+E) log V) | O(VE) |
| Approach | Greedy | Dynamic Programming |
| Implementation | Priority queue | Simple loop |
| Best for | Non-negative weights, speed | Negative weights, simplicity |
Negative Cycle Detection
A negative cycle is a cycle whose total edge weight is negative. If such a cycle is reachable from the source, then shortest paths to some vertices are negative infinity (keep going around the cycle). Bellman-Ford detects this: if after V-1 iterations any edge can still be relaxed, the graph has a reachable negative cycle.
Applications
- Currency arbitrage detection: Currencies as vertices, exchange rates as log-edges. A negative cycle means profitable circular exchange.
- Network routing: Distance vector protocols (like RIP) use Bellman-Ford
- Constraint systems: Solving systems of difference constraints
- As a subroutine: Johnson's all-pairs algorithm uses Bellman-Ford to reweight edges
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Bellman-Ford Algorithm.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Data Structures & Algorithms topic.
Search Terms
data-structures-algorithms, data structures & algorithms, data, structures, algorithms, graphs, bellman, ford
Related Data Structures & Algorithms Topics
Continue learning this concept
GraphsBreadth-First Search (BFS) AlgorithmLearn BFS traversal with queue-based implementation, level-order processing, shortest path in unweighted graphs, and real applications.GraphsDepth-First Search (DFS) AlgorithmMaster DFS traversal using recursion and stack, understand pre/post ordering, cycle detection, and connected component discovery.GraphsDijkstra\Master Dijkstra\GraphsFloyd-Warshall AlgorithmMaster the all-pairs shortest path algorithm using dynamic programming with three nested loops, path reconstruction, and practical applications.GraphsKruskal\Learn Kruskal\GraphsPrim\Master Prim\