beingsde
Sign In
Back to all DSA patterns
Graph / Shortest Path•Pattern: Dynamic Programming / Edge Relaxation•Medium

Bellman-Ford — detect negative weight cycles

Problem Intuition & Objective

Find shortest paths and detect negative cycles in a weighted directed graph.

Time ComplexityO(V×E)
Optimal
Space ComplexityO(V)
Memory Bounds
Optimal Algorithmic Approach

V-1 edge relaxation passes.

Core Invariants & Edge Cases

  • Relax all edges V-1 times (guarantees shortest paths if no negative cycle)
  • A V-th relaxation that still reduces a distance means a negative cycle exists
  • Handles negative edges unlike Dijkstra
Previous ProblemTopological sort of a DAG (Kahn's algorithm)Next Problem Union-Find — connected components with dynamic union

System Design & Architecture Roadmap

Coding interviews are only 50% of the bar. Master High-Level Design, distributed systems, and Object-Oriented LLD.

60+ HLD QuestionsSharding, caching, and real-time distributed systems.27 LLD BlueprintsObject-oriented design patterns with class diagrams.SDE Quick ReferenceLatency numbers and database selection matrix.