All subjects · Mathematics · WDM11 (D1)

Dijkstra: directed networks and multiple routes

Dijkstra's algorithm also works when edges are one-way, and exam questions often twist the problem: two shortest routes, a route via a given vertex, or a new start point.

Directed edges

In a directed network an edge can only be used in the direction of its arrow. When updating from vertex X, only look at arcs that leave X. Tracing back works the same way, following arrows backwards.

More than one shortest route

When tracing back, check every arc into the current vertex. If two arcs both pass the test final(Y) - final(X) = weight, there are two shortest routes; give them all if asked.

Adapting the problem

Shortest route via V: find the shortest S to V and V to T separately and add.
New start: rerun from that vertex.
A road closed: delete that edge and rerun, or check whether it was used.

Always quote the length and the route.

Worked example

Use Dijkstra's algorithm on directed network H to find the shortest route from S to T.

Order of final values: S 0, C 3, A 4, B 6, E 10, D 11, T 14
Trace back from T: arcs into T passing the test give the routes SABDT and SABEDT and SCBDT and SCBEDT

Answer: Shortest length 14, by SABDT or SABEDT or SCBDT or SCBEDT

Key idea: Follow arrow directions; check every arc when tracing back, as there may be several shortest routes; split 'via' problems into two parts.

Check yourself

Find the length of the shortest route from S to T in directed network H.
Show answer
14. Final values: S 0, C 3, A 4, B 6, E 10, D 11, T 14.
How many different shortest routes from S to T are there in directed network H?
Show answer
4. Tracing back gives SABDT and SABEDT and SCBDT and SCBEDT.
What is the final value of B when Dijkstra's algorithm is applied to directed network H from S?
Show answer
6. Working values at B: 7, 6. The final value is 6.
Find the length of the shortest route from S to T in directed network H that passes through A.
Show answer
14. S to A: 4. A to T (run from A): 10. Total 14.
In a directed network, when vertex X receives its final value, which vertices get new working values?
- All vertices joined to X by any arc
- Vertices at the start of arcs entering X
- Vertices at the end of arcs leaving X
- Every vertex without a final value
Show answer
Vertices at the end of arcs leaving X. You can only travel along an arc in its direction, so only arcs out of X are used.
In directed network H, the arc E to D is closed. Does the shortest distance from S to T change?
- No, because a shortest route that avoids E to D still exists
- Yes, it increases by 1
- Yes, T can no longer be reached
- Yes, it decreases
Show answer
No, because a shortest route that avoids E to D still exists. The shortest routes are SABDT and SABEDT and SCBDT and SCBEDT. At least one avoids E to D, so the length stays 14.

Practise with instant feedback

Sources

Last updated 7 November 2026. Spotted a mistake? Tell us.