TRT
Sign in

Advanced · Module 17 · Lesson 1 of 4

Dijkstra's algorithm

With non-negative edge weights, the unsettled vertex with the smallest tentative distance can never be improved, so Dijkstra's algorithm settles vertices one at a time in distance order, using a min-heap.

Pro — members onlyAbout 15 minutes

By the end you can

  • Run Dijkstra's algorithm with a min-heap and lazy deletion of stale entries
  • Explain why a popped vertex's distance is final when all weights are non-negative
  • State its cost, recover paths, and adapt it to bottleneck problems

Builds on Breadth-first search, Top-k and merging streams.

01 · A question first

A navigation app finds the fastest route across a city of a million intersections in milliseconds. Breadth-first search counts streets, but streets take different times to drive. Which intersection should the search finish next, and why can that answer never be improved later?

Make a guess before you read on.

02 · The idea

Members only

Unlock the full lesson

This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.

What's inside

  • Weighted shortest paths
  • Settle the closest vertex next
  • Why the popped distance is final
  • Lazy deletion
  • Cost
  • Other path costs
  • Mistakes to watch for
  • Where it runs
See plansAlready a member? Sign in

03 · Practice

Practice · medium · LeetCodeNetwork delay timeFind how long a signal takes to reach every node of a weighted directed network, with Dijkstra from the source.Practice · medium · LeetCodePath with minimum effortFind the route across a height grid whose largest single climb is as small as possible, with Dijkstra on bottleneck costs.Practice · hard · LeetCodeSwim in rising waterFind the earliest time you can swim across a grid as water rises, by minimizing the highest cell on the path with Dijkstra.

Asked in interviews

Something wrong with this lesson? Report a problem