Back to course

Lesson 42: Dijkstra's Algorithm: Introduction and Greediness

Algorithms: From Zero to Hero (A Beginner's Guide)

42. Dijkstra's Algorithm: Introduction and Greediness

Dijkstra's Algorithm solves the single-source shortest path problem for a weighted graph with non-negative edge weights.

Core Concept: Greedy Approach

Dijkstra's is a Greedy Algorithm. At every step, it makes the choice that looks best at the moment, hoping that this local optimum will lead to a global optimum.

  1. Start at the source node, setting its distance to 0 and all others to infinity.
  2. Repeatedly select the unvisited node that currently has the smallest known distance from the source.
  3. 'Visit' that node and update the distances of all its neighbors.

Data Structure Requirement

Dijkstra's uses a Min Heap (Priority Queue) to efficiently find the unvisited node with the smallest distance in O(log N) time, making the overall complexity highly efficient.