Weighted Shortest Paths

MIT 6.006 Introduction to Algorithms, lecture 11, 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 how the course changes from counting the number of edges in a path to adding up a weight, an integer number, on each edge.

Key ideas

Until now, a path's length was just the number of edges (connections) it used. From here on, each edge gets an integer weight, and a path's length is the sum of those weights. 3:28
Weights are useful in real life. Roads take different amounts of time to drive, so a road that takes longer should count for more than a quick one. 5:43
Weights can be positive, negative, or zero. In this class they are always whole numbers, not decimals. 4:10
The course assumes that, given two vertices, you can look up the weight of the edge between them in constant time, meaning the lookup takes the same short time no matter how big the graph is. 9:49

Words to know

weight: A number attached to an edge that stands for its cost, such as distance or travel time. It replaces the simple count of 1 per edge.
integer: A whole number, positive, negative, or zero, with no fractions or decimals.
adjacency list: A way to store a graph where each vertex keeps a list of the vertices it connects to directly.
hash table: A storage method that lets you find a stored item very quickly by its key, almost instantly no matter how many items there are.

Example

Think of driving between two towns. Counting roads is like counting turns, but a road that takes 30 minutes to drive should count for more than one that takes 5 minutes. Adding up the minutes on each road tells you which route is really quickest, and that is the idea of adding weights to edges.

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

Part 2 · 10:00–20:00

This part explains how adding weights (numbers) to edges changes what a shortest path means, and what can go wrong when some weights are negative.

Key ideas

With weighted edges, the weight of a path is the sum of the weights of all its edges. The shortest path is the path between two vertices with the smallest total weight. 10:46
A weighted path can use the same edge more than once, and each use is counted again in the total. This matters later, when edges can have negative weights. 12:00
If there is no path between two vertices, the shortest distance is set to infinity by convention. 15:11
Negative weights can cause trouble. If you can loop around a cycle whose total weight is negative, each loop makes the path cheaper, so there is no smallest value and the shortest distance becomes minus infinity. 18:27
The problem only matters when a negative weight cycle can be reached from the starting vertex. If it can, any vertex you can get to after passing through that cycle has a shortest distance of minus infinity. 19:56

Words to know

weight: A number attached to an edge, like a cost or a distance. A path's weight is the sum of the weights of its edges.
infimum: The lowest value that a set of numbers gets closer and closer to, even if it never actually reaches it. The lesson uses it when a path can keep getting shorter forever.
negative weight cycle: A loop of edges that starts and ends at the same vertex and has a total weight below zero. Going around it again always makes the path cheaper.
infinity: A value bigger than any number. The lesson uses it as the shortest distance when no path exists.

Example

Imagine a loop of roads where every trip around the loop pays you a little money. If you could drive around it forever, your total earnings would keep dropping toward no bottom, so there would be no single best amount to name. That is what a negative weight cycle does to a shortest path.

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

Part 3 · 20:00–30:00

This part explains when weighted shortest paths can be solved with simpler tools, such as BFS or a DAG method, and why negative weight cycles break the idea of a shortest path.

Key ideas

A negative weight cycle can be looped around again and again to make the path shorter forever, so there is no shortest path to return. The lesson sets the distance to minus infinity in that case. 20:00
If every edge has weight 1, or every edge has the same positive weight, then BFS can solve the weighted problem. You divide by that shared weight, run BFS, and multiply back afterward. 21:55
An edge with weight 4 can be copied as a chain of four edges of weight 1. This only gives a fast linear-time method when the total of all the weights is small compared with the number of vertices and edges. 23:28
If the graph is a DAG (a directed graph with no cycles), shortest paths can be found in linear time for any edge weights, because the graph's shape is what matters, not the weights. 25:18
You can rebuild the parent pointers for shortest paths from the shortest distances alone, in linear time, so you do not need to track both during the algorithm. 29:19

Words to know

negative weight cycle: a loop of edges whose weights add up to a negative number, so going around it again makes the total smaller.
DAG: Directed Acyclic Graph: a set of arrows between points where you can never follow the arrows and end up back where you started.
parent pointer: a note at each vertex saying which vertex came just before it on the shortest path, so you can trace the path back to the start.
shortest path tree: the set of shortest routes from one starting point to every other point, drawn as a tree that branches out from the start.

Example

Imagine walking through a city where every block counts as one step, and a long avenue counts as four blocks. You could count it as four separate short steps, which makes the walk easy to count, but if the avenue were 1000 blocks long, that counting would take far too long.

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

Part 4 · 30:00–40:00

This part shows how to find the shortest route from one starting point to every other point in a DAG (a graph with no loops, where you can only move one way), and how to record the route using parent pointers.

Key ideas

A parent pointer tells you which vertex comes right before another one on a shortest path. The lesson only needs these for vertices whose shortest path distance is finite, meaning the vertex can actually be reached. 30:00
You can find a vertex's parent by checking each outgoing edge. If the shortest distance to the first vertex plus the edge's weight equals the shortest distance to the second vertex, the first vertex is a parent along a shortest path. 34:09
Finding parents takes linear time, the same kind of effort as breadth-first or depth-first search. So the lesson will first compute the distances and only then compute the parents. 35:20
DAG relaxation starts every distance estimate at infinity, which is a safe overestimate. Then it keeps lowering the estimates while never letting them drop below the true shortest distances. 37:29
An estimate is lowered whenever it breaks the triangle inequality, which is the rule that a direct route should never be longer than a route that goes through another point. 39:02

Words to know

parent pointer: A note that says which vertex comes just before a given vertex on a shortest path, so you can trace the route back.
DAG: Directed acyclic graph: a set of points joined by one-way arrows, with no loops that let you go back to where you started.
distance estimate: A guess of how short the path to a point is, which starts as a very large number and gets smaller as you learn more.
triangle inequality: The idea that going straight from one point to another is never longer than going through a third point on the way.

Example

Imagine you are guessing how long it takes to drive from home to each town on a map. You start by assuming every town is very far away. Each time you find a faster road through another town, you lower your guess for that town, and you keep doing this until no better road is left.

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

Part 5 · 40:00–50:00

This part explains how an algorithm slowly improves guesses of shortest distances by checking each edge against a rule called the triangle inequality.

Key ideas

The triangle inequality says the shortest distance from u to v can never be longer than going from u to some other vertex x and then from x to v. Going through x is just one possible path, so the true shortest path cannot be worse. 41:04
If an edge breaks this rule in our current guesses, the guesses must be wrong. We fix that by lowering the guess for the end vertex. 42:44
Relaxing an edge means lowering the distance guess for v to equal the guess for u plus the weight of the edge from u to v. This fixes that one rule, though it may break others elsewhere. 44:25
Relaxing is safe because every guess is either infinity or the weight of some real path. A guess never becomes a made-up number that no path could produce. 44:47
The DAG relaxation algorithm starts every guess at infinity, sets the starting vertex to 0, then goes through the vertices in topological sort order and relaxes each outgoing edge. 49:09

Words to know

triangle inequality: A rule saying a direct route between two points is never longer than a detour through a third point.
relax: In this lesson, to lower a distance guess so that one broken rule is fixed. The word is just a label that stuck.
distance estimate: Our current best guess of how short the path to a vertex is. It can be too high at first and gets lowered over time.
topological sort: An order to visit the vertices so that every edge points forward, from earlier vertices to later ones.

Example

Imagine you guess that a town is 60 minutes away by car. Then you find a side road that gets you there in 40 minutes, so your guess was wrong and you lower it to 40. This is like relaxing an edge, because you update the guess to fix a rule your current guess broke.

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

Part 6 · 50:00–57:27

This part shows how to find shortest paths in a graph with no loops by visiting the vertices in a fixed order and updating distance estimates as you go.

Key ideas

A topological order lists every vertex so that all edges point forward. A graph with this kind of order has no loops, so you can go through the vertices one by one. 50:55
Relaxing an edge means checking whether going through that edge gives a shorter route to a vertex. If it does, you replace the old estimate with the new, smaller number. 50:00
Start every estimate at infinity, except the start vertex, which gets 0. Vertices that come before the start in the order can never be reached, so they stay at infinity. 52:07
Walk through the vertices in topological order and relax every edge going out of each one. When you reach a vertex, all the vertices before it are already correct, so its estimate is also correct. 55:16
Every vertex and edge is handled a fixed number of times, so the total work grows in a straight line with the size of the graph. The lecturer calls this linear time. 57:08

Words to know

Topological sort order: A line-up of all the vertices where every edge points from an earlier vertex to a later one, so no edge goes backward.
DAG: Short for directed acyclic graph: a graph whose edges all have a direction and that has no loops, so a topological order exists.
Relax: To test whether a new route is shorter than the current estimate, and to update the estimate if it is.
Triangle inequality: The rule that a direct route to a vertex should never cost more than a detour through another vertex. When it is broken, you can improve the estimate.

Example

Think of getting ready for work, where some tasks must come before others, like putting on socks before shoes. If you do the tasks in an order that respects those rules, you never have to go back and redo an earlier step. This is only an everyday comparison to help the idea of topological order make sense.

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

← Lecture 10: Depth-First Search · Lecture 13: Dijkstra →

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