Optimisation algorithms

Overview

Recall questions on what Dijkstra's algorithm computes, what is recorded for each vertex, why weights must be non-negative, and recovering the path itself.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   What problem does Dijkstra's shortest path algorithm solve?

   Model answer

   It finds the shortest, meaning lowest total weight, path from a chosen starting vertex to every other vertex in a weighted graph — or to one particular destination vertex. The lengths of the edges are taken into account, not merely the number of edges.

2. 2

   Why can breadth-first search not be used in place of Dijkstra's algorithm on a weighted graph?

   Model answer

   Because breadth-first search counts edges rather than weights, so it finds the route using the fewest edges. In a weighted graph a route with more edges can easily have a smaller total weight — a motorway detour may be quicker than a single slow lane — so the fewest-edge route is not necessarily the cheapest, and a weight-aware algorithm is needed.

3. 3

   A weighted graph has vertices A, B, C and D with undirected edges A-B of weight 1, A-C of weight 4, B-C of weight 2, B-D of weight 6 and C-D of weight 3. Trace the shortest path from A to D.

   Model answer

   From A, B is reached at cost 1 and C at cost 4. Going on from B, C can be reached at 1 + 2 = 3, which is cheaper than the direct 4, so C's best known distance becomes 3 by the route A, B, C; and D can be reached at 1 + 6 = 7. Going on from C at distance 3, D can be reached at 3 + 3 = 6, which is cheaper than 7, so D's best known distance becomes 6. The shortest path from A to D is A, B, C, D with total weight 6.

4. 4

   A weighted graph has vertices P, Q, R and S with undirected edges P-Q of weight 2, P-R of weight 5, Q-R of weight 1 and R-S of weight 4. Find the shortest distance from P to every other vertex.

   Model answer

   Q is reached from P directly at cost 2. R can be reached directly at 5, or via Q at 2 + 1 = 3, so its shortest distance is 3 by the route P, Q, R. S can only be reached through R, at 3 + 4 = 7 by the route P, Q, R, S. So the shortest distances from P are: Q = 2, R = 3, S = 7.

5. 5

   In a trace of Dijkstra's algorithm, what is recorded for each vertex?

   Model answer

   The best distance from the start vertex found so far, which begins as infinity for every vertex except the start (which is zero) and is reduced whenever a cheaper route is discovered; the previous vertex on that best route, so that the path itself can be reconstructed at the end by working backwards; and whether the vertex has been finalised, meaning its shortest distance is now known for certain and it will not be examined again.

6. 6

   Once Dijkstra's algorithm has finished, how is the actual path recovered rather than just its length?

   Model answer

   By following the record of previous vertices backwards. Start at the destination, look up the vertex recorded as coming before it on its best route, then look up that vertex's predecessor, and so on until the start vertex is reached. Reversing the sequence obtained gives the shortest path in the forward direction.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.