Dijkstra

MIT 6.006 Introduction to Algorithms, lecture 13, explained in plain English

Want this lecture to stick? In LessonBound you get checked practice questions for every part, can ask about anything you don't get, and can listen with your screen off. Free, no ads.

Learn this lecture free

Watch or read the original lecture: MIT OpenCourseWare.

Part 1 · 0:00–10:00

This part explains why shortest paths can be found faster when no edge has a negative weight, by growing outward from the start vertex one distance step at a time.

Key ideas

Earlier methods were either fast only for special graphs or slow for general ones. Bellman-Ford handles any graph but can take about V times E steps, which is slow for dense graphs. 3:28
If no edge has a negative weight, we can skip negative-cycle trouble and get a running time that is almost linear, with only a small logarithmic factor on the vertex count. 4:31
The new idea is to grow a ball around the source vertex, exploring the closest vertices first, and to work out the distances as we go instead of knowing them in advance. 7:04
With non-negative weights, distances never shrink as you move along a shortest path. A vertex further along the path is always at least as far from the source as the vertex before it. 8:28

Words to know

invariant: A rule that stays true at every step of a process. Here, the distances we have already found stay correct as the algorithm keeps going.
relaxing: Checking an edge and updating a stored distance when you find a shorter route through it.
monotonically: Always moving in one direction. Here, distances going up along a path, or staying the same, but never going down.
dense: A graph with a lot of edges, close to every possible pair of vertices being connected.

Example

Think of driving from home to a friend's house and passing a gas station on the way. The total trip can never be shorter than the drive to the gas station, because the rest of the trip only adds distance. That is why, with no negative weights, the distance to a vertex is never less than the distance to any vertex before it on the path.

3 checked practice questions for this part are in the app.

Part 2 · 10:00–20:00

This part explains why Dijkstra's method needs edge weights that are never negative, and how knowing the order of vertices by distance can make shortest-path search fast.

Key ideas

Dijkstra's method works because a path's total weight can never be less than the path it grows from, since no edge weight is negative. So the area within a given distance of the start grows outward in a clean way. 10:00
If an edge had a very negative weight, a vertex far away could suddenly become close to the start. That breaks the clean outward growth, so the method would fail. 10:18
If you already know the order of the vertices from closest to farthest from the start, shortest paths can be found in linear time, which means the work grows in step with the size of the graph. 11:38
In that order, an edge that points backward is only useful in a shortest path if its weight is zero. 15:35
Vertices at the same distance joined by a zero-weight edge can be put in either order. Flipping them does no harm, so every useful edge can then point forward. 18:43

Words to know

Negative weight: A cost on an edge that is below zero, so going along it makes the total path shorter instead of longer.
DAG: Directed acyclic graph: a set of points joined by one-way arrows that never loop back around to where they started.
Zero-weight edge: A connection between two points that adds no cost to the path.
Linear time: A way of measuring work where doubling the size of the problem roughly doubles the time it takes.

Example

Imagine hiking away from a campsite where every step on the trail takes you farther from camp, so your distance only grows. Now imagine a trail with a shortcut that suddenly brings you back close to camp. The first trail is easy to track outward, but the shortcut makes that tracking go wrong, which is the problem negative weights cause.

3 checked practice questions for this part are in the app.

Part 3 · 20:00–30:00

This part introduces Dijkstra's algorithm, which finds shortest paths in a weighted graph with non-negative weights by always handling the closest unfinished vertex next, using a special priority queue.

Key ideas

If you already knew the vertices in order of increasing distance from the start, you could find all shortest paths in one pass. Dijkstra's algorithm uses this same idea. 20:43
Dijkstra's algorithm relaxes edges (checks and improves distance estimates along them) starting from the vertices with the smallest distance from the source. It is a weighted version of BFS. 22:59
The algorithm needs a quick way to find the next closest vertex. It uses a data structure called a changeable priority queue for this. 23:28
A changeable priority queue can build from a set of items, remove the item with the smallest key, and lower the key of a specific item found by its ID. 24:27
You can build a changeable priority queue from a normal priority queue plus a dictionary that maps each ID to that item's place in the queue. Vertex IDs are numbers from 0 to V minus 1, so the dictionary can be a direct access array for fast lookups. 27:38

Words to know

priority queue: A list where you can always take out the item with the smallest value (its key) first.
changeable priority queue: A priority queue that also lets you find an item by its ID and make its key smaller.
relax: To check whether a path through an edge gives a shorter distance, and if so, update the distance estimate.
direct access array: A simple list where you find an item right away by its number, like going straight to shelf number 7.

Example

Think of a to-do list sorted by due date, where the item due soonest is always at the top. If you learn that one task is now more urgent, you move that task up by its name or number, and the list reorders itself. The changeable priority queue works the same way with distance estimates.

3 checked practice questions for this part are in the app.

Part 4 · 30:00–40:00

This part explains how Dijkstra's algorithm keeps a list of distance guesses, always picks the closest unfinished vertex, and updates its neighbors, then runs it on a small example.

Key ideas

Dijkstra's algorithm only works when every edge weight is non-negative, which means no edge has a cost below zero. That is why no shortest distance can drop below 0. 30:00
The algorithm keeps a priority queue (a list that always gives back its smallest item) of every vertex, keyed by its current distance guess. Each round, it removes the vertex with the smallest guess. 31:44
When a vertex is removed, the algorithm relaxes its outgoing edges. Relaxing means checking whether the route through that vertex is shorter than the current guess, and if so, replacing the guess with the shorter value. 33:22
After a guess gets smaller, the queue must be told, so it can reorder itself and still hand back the correct smallest vertex next. 34:04
In the example, the algorithm finishes with shortest distances of 0 for s, 3 for c, 7 for a, 9 for b, and 5 for d. The lesson says proving these results are correct takes two main observations. 39:19

Words to know

relax: To check whether a path through a vertex gives a shorter distance to a neighbor, and if it does, update the neighbor's distance guess to that shorter value.
priority queue: A line of items where the item with the smallest key always comes out first. Here, the key is the distance guess.
triangle inequality: The rule that a direct path between two points is never longer than a path that goes through a third point. A relaxation fixes a spot where this rule is broken.
edge weight: The cost or length of traveling along one edge (one connection) between two vertices (points) in a graph.

Example

Think of planning a road trip. You always go to the nearest town you have not yet visited, then check whether the road through that town gets you to other towns faster than you knew before. Dijkstra works the same way: it always picks the closest unfinished vertex and checks whether it can shorten the route to its neighbors.

3 checked practice questions for this part are in the app.

Part 5 · 40:00–50:00

This part explains why Dijkstra's method, once it finishes, has found the true shortest distance to every vertex, using a proof by induction.

Key ideas

The goal is to show that when Dijkstra finishes, every distance estimate equals the true shortest-path distance. The proof rests on two observations. 40:20
Relaxation only ever lowers a distance estimate, and it is safe, meaning each new value is the length of some real path. So a correct estimate can never be changed to a wrong one later. 41:18
Since every vertex gets removed from the queue, it is enough to show that each vertex's estimate is correct at the moment it is removed. 43:34
The proof uses induction, which means it checks the first case, then shows that if the claim holds for earlier vertices, it holds for the next one. 43:55
The last step works because the priority queue always removes the vertex with the smallest estimate, and non-negative weights mean a shortest path never gets shorter as it goes on. 49:31

Words to know

relaxation: Checking whether a path through one vertex gives a shorter route to the next vertex, and if so, updating the distance estimate to the shorter value.
induction: A proof method: show the claim is true for the first step, then show that if it is true up to some step, it must also be true for the next step.
priority queue: A list that always gives back the item with the smallest value first, here the vertex with the smallest distance estimate.
subpath: A piece of a longer path, from its start to some point along the way. A piece of a shortest path is also a shortest path to that point.

Example

Imagine you are planning trips from home to several towns, and you keep a note of the shortest known trip to each one. You always go to the closest town you have not yet visited, and any shorter route you find updates your note. Once you visit a town, its note is final, because no shorter route can turn up later.

3 checked practice questions for this part are in the app.

Part 6 · 50:00–57:16

This part explains how fast Dijkstra's algorithm runs, and how the choice of priority queue changes that speed.

Key ideas

Dijkstra's running time is counted in queue operations. Building the queue happens once, removing the minimum happens once per vertex, and lowering a key happens once per outgoing edge, so the total is B + V×M + E×D. 51:26
A plain array is the simplest priority queue. Lowering a distance is fast, but finding the minimum means checking every entry, which gives a time close to V squared. That is fine for dense graphs, where the number of vertices is large compared to the edges. 52:18
A binary heap makes both finding the minimum and lowering a key take logarithmic time. The total becomes E log V, which works well for sparse graphs, where the number of edges is at most V. 53:45
A Fibonacci heap gets the best theoretical time, E + V log V, but it is more complicated and is rarely used in practice. Most people choose an array for dense graphs or a binary heap for sparse graphs. 55:55
Bellman-Ford is slower, with a quadratic bound. The lecture says it is needed when there might be negative cycles in the graph, and that faster algorithms exist but are not taught in this class. 56:45

Words to know

priority queue: A list that always lets you quickly grab the item with the smallest value, and lets you change values as you go.
decrease key: Lowering the value stored for an item already in the queue, such as lowering a distance when a shorter path is found.
sparse graph: A graph with relatively few edges. The lecture describes it as one where the number of edges is at most the number of vertices.
binary heap: A tree-shaped way of storing items so the smallest is always easy to find. Adding or changing an item takes only about log-many steps.

Example

Think of a to-do list where you always need the most urgent task. If you keep the list unsorted, changing a task is quick, but finding the most urgent one means reading the whole list. A sorted or tree-shaped list makes finding the most urgent task quick, at the cost of a bit more work each time you make a change.

3 checked practice questions for this part are in the app.

← Lecture 11: Weighted Shortest Paths · Lecture 15: Dynamic Programming, Part 1: SRTBOT, Fib, DAGs, Bowling →

Notes written by AI (Claude) from the lecture's official transcript, so check anything important against the lecture. MIT OpenCourseWare · CC BY-NC-SA 4.0 · not affiliated with or endorsed by MIT. These notes are shared under the same license.

LessonBound · Free lecture notes · Privacy · Terms · New York