Interview OS
Back to Algorithms & Data Structures

Library

Shortest paths (Dijkstra / Bellman-Ford)

Weighted shortest paths.

Graph

Overview

Shortest-path algorithms find minimum-cost routes: BFS for unweighted graphs, Dijkstra for non-negative weights, and Bellman-Ford when negatives are possible. Picking the right one hinges on the edge weights.

How it works

Graph
InputRelaxSelectOutputWeightedw(e)Edge relaxd[v]=minMin heapPQDistances
ClientServiceDataEdge

Step by step, with examples

  1. 1

    Weighted

    • Non-negative → Dijkstra; negatives → Bellman-Ford.
  2. 2

    Edge relax

    • Update a distance if a shorter path is found.
  3. 3

    Min heap

    • Pick the closest unsettled node.
  4. 4

    Distances

    • Return shortest distances/paths.
    • Example: GPS routing

Overview

Dijkstra (non-negative weights, heap, O(E log V)); Bellman-Ford handles negative edges and detects negative cycles.

When to use it

  • Routing
  • Network latency
  • Cheapest-cost paths

Common pitfalls

  • Dijkstra with negative edges
  • Forgetting to relax all edges in Bellman-Ford

Where this content comes from

For full transparency, this content is curated and verified from these sources:

CLRS — Introduction to AlgorithmsCurated competitive-programming archivesOppZen-authored algorithm guides