beingsde
Sign In
Back to all DSA patterns
Graph / Shortest Path•Pattern: Greedy + Min-Heap•Medium

Dijkstra's shortest path algorithm

Problem Intuition & Objective

Find the shortest path from a source to all nodes in a weighted graph with non-negative edges.

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

Min-heap Dijkstra: process each node when it's popped from the heap.

Core Invariants & Edge Cases

  • Priority queue (min-heap) ordered by distance
  • Relax neighbors: if dist[u] + w < dist[v], update dist[v]
  • Works only for non-negative weights
Previous ProblemPalindrome partitioningNext Problem Topological sort of a DAG (Kahn's algorithm)

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.