Back to the on-screen lesson ·
One number per node instead of a list of routes: settle the nearest, relax its arcs, repeat.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to compute the shortest distance to each node of a small network, give the order in which Dijkstra's method settles the nodes, say why settling is safe only with non-negative arc lengths, match each shortest-path method to the case it covers, and find the range of an arc length over which the shortest route does not change.
You can write a network as balance rows. A shortest path is one unit of flow sent from the source to the sink at least cost, so everything in this lesson is a linear program being solved by a method that knows what kind of program it is.
A node's tentative distance is the best total found to it so far. To relax an arc is to check whether going along it improves the tentative distance at its far end. To settle a node is to declare its tentative distance final, which Dijkstra's method does to the nearest unsettled node at each step.
Dijkstra's method keeps one number per node — the best distance found so far — rather than a list of routes. At each step it takes the nearest unsettled node, declares that number final, and relaxes the arcs leaving it: for each, if the settled distance plus the arc's length beats the far end's tentative distance, it replaces it.
Why settling is safe. Any route to the chosen node through a node that is still unsettled would have to pass through something already at least as far away, and every further arc adds a non-negative amount. So no such route can be shorter. That argument is the whole correctness proof, and it uses non-negativity in one place.
When it fails. With a negative arc, a route discovered later can improve a node that has already been settled, and nothing goes back. Bellman-Ford covers that case by relaxing every arc repeatedly, more slowly, and detects a negative cycle — the situation in which no shortest path exists at all.
The cost is a small multiple of the number of arcs, and no path is ever written out. That is why the method runs on road networks with millions of nodes.
Another way: steps
Another way: example
From $S$: $a = 4$, $b = 2$. Settle $b$; relax $b \to a$ at cost $1$, so $a = 3$; relax $b \to t$ at cost $5$, so $t = 7$. Settle $a$; relax $a \to t$ at cost $3$, so $t = 6$. Settle $t$: the route is $S$, $b$, $a$, $t$.
A shortest path is assumed to be a single arc when one exists, which the second row of almost any example disproves. The other error is applying Dijkstra to a graph with a negative arc and trusting the answer: the method does not fail loudly, it settles a node too early and reports a wrong number.
A direct arc $S \to T$ of length $10$, and a two-step route of lengths $3$ then $4$.
Two routes.
The detour totals $7$, which is less than $10$.
Add along each route.
So the shortest path has two arcs. Fewer arcs is not shorter, and nothing in the problem rewards directness.
Length, not hops.
Both totals come to $6$.
Add along each.
So the shortest distance is $6$, and there are two shortest paths — the distance is unique, the path need not be.
From $S$: an arc to $A$ of length $10$ and an arc to $B$ of length $2$; from $B$, an arc to $A$ of length $3$ and an arc to $T$ of length $18$; from $A$, an arc to $T$ of length $1$. Fill in the shortest distance to each node.
| Shortest distance from $S$ | |
|---|---|
| Node $A$ | |
| Node $B$ | |
| Node $T$ |
In the same network — $S$ to $A$ at $11$, $S$ to $B$ at $3$, $B$ to $A$ at $2$, $B$ to $T$ at $19$, $A$ to $T$ at $1$ — put the nodes into the order Dijkstra's method settles them.
Number the steps in order (write the number in the box):
How long is the shortest path between the two nodes: routes of total lengths $7$, $9$ and $12$?
Answer:
A graph has an arc of length $-4$ somewhere in it. Why can Dijkstra's method fail on it?
A shortest-path problem on $6$ nodes can be attacked several ways. Match each method to the case it is right for.
| Every arc length is non-negative | Arc lengths may be negative | Every arc has the same length | The graph has no cycles | |
|---|---|---|---|---|
| Dijkstra's method | ||||
| Bellman-Ford | ||||
| Breadth-first search | ||||
| One pass in topological order |
The only route from $S$ to $T$ other than the direct arc totals $8$. For which lengths $L$ of the direct arc is that arc a shortest path? Give the interval.
This task has no paper form; do it on a device.
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
From $S$: an arc to $A$ of length $11$ and an arc to $B$ of length $4$; from $B$, an arc to $A$ of length $4$ and an arc to $T$ of length $10$; from $A$, an arc to $T$ of length $2$. Fill in the shortest distance to each node.
| Shortest distance from $S$ | |
|---|---|
| Node $A$ | |
| Node $B$ | |
| Node $T$ |
You can run Dijkstra's method on a small network and say why it settles nodes in order of distance. Say in your own words why a negative arc length breaks the argument that settling is safe.
7. Your turn: two routes total $2 + 2 + 2$ and $3 + 3$. What is the shortest distance?, step 2