A shortest route and a changed edge

Choose your method, connect the parts and explain your conclusions. These original questions include written reasoning and sketches as well as exact answer checks.

Suggested marks guide how much working to show. The site does not automatically award examination marks for proofs, diagrams or methods. Use scaffolded fluency practice when you need a hint first.

Decision option. Course filters use selected objective mappings; none of these tasks establishes complete paper coverage.

Before you start

Shortest paths with Dijkstra’s algorithm. Read the relevant method, then decide which parts you can solve without hints.

Check a misconception first · Try a connected problem

Read an original example question

An undirected network has positive edge weights. Find a route from A to F.

Every connection and weight is also given in the table. The network is not drawn to scale.

Question data
Edge	Weight
AB	2
AC	5
BC	1
BD	4
CD	1
CE	4
DE	1
DF	4
EF	1

Part a

Use Dijkstra’s algorithm to find the shortest distance.

Part b

State a shortest route and show your labelled-node working.

Part c

The edge BC now has weight 5; all others are unchanged. Find the new shortest distance.

Part d

Explain why Dijkstra’s usual settled-node rule depends on nonnegative weights.

Model solution and review criteria

Part a

Permanent distances are A:0, B:2, C:3, D:4, E:5, F:6. Record tentative updates and predecessors as each node is settled.

Start at A and update adjacent tentative distances.
Settle the least tentative node each time.
Record predecessors as well as lengths.

Part b

A–B–C–D–E–F follows the predecessor chain. A route length alone does not demonstrate the algorithm.

Give the full route.
Show settled and tentative labels in a table.

Part c

A–C–D–E–F has length 8; A–B–D–E–F also has length 8. Recompute labels: the old route is no longer shortest.

Recompute rather than changing only the old route length.
Accept either tied shortest route in the explanation.

Part d

A later path through a negative edge could improve a supposedly final label. Positive weights justify the settled-node guarantee; negative-edge graphs need a suitable different method.

Explain the guarantee that would fail.

Compare your own reasoning. No automatic examination marks are awarded.