Shortest Path (Bellman-Ford / BFS+K) — Graph Traversal Patterns (DFS & BFS)

The Shortest Path (Bellman-Ford / BFS+K) pattern applies when you need the Shortest Path (Bellman-Ford / BFS+K) technique within the Graph Traversal Patterns (DFS & BFS) pattern. Its time complexity is O(V × E) and space complexity O(V). It is used in 2 problems on Thita, including Cheapest Flights Within K Stops and Shortest Path with Alternating Colors. Common variations are Graph DFS - Cycle Detection (Directed Graph) and Deep Copy / Cloning.

Find shortest paths with constraints using Bellman-Ford algorithm and BFS with limited stops.

Shortest Path (Bellman-Ford / BFS+K) is one of the 12 subpatterns of the Graph Traversal Patterns (DFS & BFS) pattern, which covers dFS/BFS traversal, topological sort, shortest paths, Union-Find, and MST. The whole pattern is about 5 hours of study. This subpattern is a depth topic for once the core techniques are automatic.

What Shortest Path (Bellman-Ford / BFS+K) covers

Master graph algorithms including DFS/BFS traversal, topological sort, shortest paths (Dijkstra, Bellman-Ford), Union-Find, and advanced graph concepts. Problems in this subpattern are usually searched for as Bellman-Ford, cheapest flights k stops, shortest path k edges, BFS constraints, leetcode 787.

How to practise Shortest Path (Bellman-Ford / BFS+K) on Thita.ai

Read the theory for Shortest Path (Bellman-Ford / BFS+K), then work the problems attached to it in the browser editor. Your solution runs against the problem's test cases, and the AI coach offers a hint about the technique you are missing rather than a finished solution. Progress is tracked per subpattern, so the Graph Traversal Patterns (DFS & BFS) tracker shows this one as covered once you have solved its problems.

Other subpatterns in Graph Traversal Patterns (DFS & BFS)

• Graph DFS - Connected Components / Island Counting — Use DFS to find connected components and count islands in grids. Flood fill and province counting problems.
• Graph BFS - Connected Components / Island Counting — Use BFS for shortest path in unweighted graphs. Solve word ladder, rotting oranges, and matrix problems.
• Graph BFS - Topological Sort (Kahn's Algorithm) — Master topological sorting using Kahn's BFS algorithm. Solve course schedule and build order problems.
• Graph DFS - Cycle Detection (Directed Graph) — Detect cycles in directed graphs using DFS with coloring (white, gray, black) approach.
• Deep Copy / Cloning — Learn to deep copy and clone graph structures using DFS/BFS with visited mapping.
• Shortest Path (Dijkstra's Algorithm) — Master Dijkstra's algorithm for finding shortest paths in weighted graphs with non-negative edges.
• Union-Find (Disjoint Set Union - DSU) — Master Union-Find data structure with path compression and union by rank for connectivity problems.
• Bidirectional BFS (BFS optimization for known source & target) — Optimize BFS by searching from both source and target simultaneously. Reduce time complexity significantly.
• Bridges & Articulation Points (Tarjan low-link) — Find bridges and articulation points in graphs using Tarjan's low-link algorithm.
• Minimum Spanning Tree (Kruskal / Prim / DSU + heap) — Find minimum spanning tree using Kruskal's or Prim's algorithm with Union-Find or heap.
• Strongly Connected Components (Kosaraju / Tarjan) — Find strongly connected components in directed graphs using Kosaraju's or Tarjan's algorithm.

Related DSA patterns

• Backtracking Patterns — Subsets, permutations, combinations, N-Queens, and word search.
• Dynamic Programming (DP) Patterns — Fibonacci, Kadane, knapsack, LCS, LIS, edit distance, grid paths, and word break.
• Bit Manipulation Patterns — XOR tricks, counting bits, power-of-two checks, and Hamming weight.
• Design Patterns — Tries, LRU/LFU cache, and data structure design.

Where to go next

Shortest Path (Bellman-Ford / BFS+K) is one lesson in a 16-pattern DSA course. If you are preparing end to end, work the interview-critical patterns first and use the pattern sheet as the checklist; if you are here for one technique, the Graph Traversal Patterns (DFS & BFS) guide is the shortest path back to the rest of it.

• The Graph Traversal Patterns (DFS & BFS) pattern guide
• All DSA patterns
• The DSA patterns sheet
• Coding practice