Practice Maths

← Graphs and Networks › Shortest Path Problems

Shortest Path Problems

Key Terms

The shortest path problem: find the minimum-weight path between two vertices
Dijkstra’s algorithm
finds shortest paths from a source vertex to all others
Algorithm assigns permanent labels (confirmed shortest distances) one vertex at a time
At each step: select the unvisited vertex with smallest tentative distance
Update neighbours: if current path + edge weight < current tentative distance, update
Repeat until all vertices have permanent labels (or the target is reached)
Dijkstra’s Algorithm:
1. Set distance to source = 0; all others = ∞
2. Select unvisited vertex with smallest distance → mark permanent
3. Update distances to neighbours:
   if dist(current) + weight(edge) < dist(neighbour): update
4. Repeat steps 2–3 until target is permanent
5. Trace back to find the path
Worked Example: Find the shortest path from A to E in the graph:
Edges: AB=4, AC=2, BC=1, BD=5, CD=8, CE=10, DE=2

StepVisitABCDE
0A042∞∞
1C0321012
2B032812
3D032810
4E032810

Shortest path A to E = 10, via A → C → B → D → E (distances 0, 2, 3, 8, 10)
Hot Tip: When tracing back the shortest path, go from the destination to the source. At each step, find the previous vertex whose permanent label + edge weight = your current vertex’s permanent label.

The Shortest Path Problem

Given a weighted graph, the shortest path between two vertices is the path with the minimum total weight (distance, cost, or time). This is one of the most practically useful problems in mathematics — it underlies GPS navigation, internet routing, and logistics.

Dijkstra’s Algorithm

Dijkstra’s algorithm systematically finds the shortest path from a source vertex to all others. It works by assigning permanent labels to vertices one at a time, always choosing the unvisited vertex with the smallest current distance estimate.

Step-by-step:

  1. Assign distance 0 to the source vertex; ∞ to all others. Mark all unvisited.
  2. Select the unvisited vertex with the smallest assigned distance. Give it a permanent label (it has been visited).
  3. For each unvisited neighbour of this vertex: calculate the distance through the current vertex. If it is less than the neighbour’s current distance, update it.
  4. Repeat steps 2–3 until the destination vertex receives its permanent label.
  5. Trace back through the permanent labels to identify the actual path.

Setting Up a Table

In exams, use a table with one column per vertex and one row per step. Bold (or circle) entries when they become permanent. Update entries in later rows when a shorter path is found.

Strategy: Always set up the table systematically. At each step, scan all unvisited vertices and select the one with the smallest value. Never select an already-visited vertex again — its label is permanent and cannot improve.

Mastery Practice

See Answers ➔
  1. Fluency A weighted graph has edges: AB=3, AC=7, BC=2, BD=5, CD=1. Find the shortest path from A to D and its total weight by inspection (the graph is small enough to enumerate paths).
  2. Fluency Using Dijkstra’s algorithm, find the shortest path from A to D in the graph: Edges: AB=6, AC=3, BC=2, BD=7, CD=4. Show your working table.
  3. Fluency A graph has edges: ST=5, SU=8, TU=3, TV=6, UV=4, VW=2. Find the shortest path from S to W and its length.
  4. Fluency In Dijkstra’s algorithm applied to a graph, the permanent labels assigned in order are: A=0, C=4, B=6, D=9, E=11. What can you say about the shortest distance from A to each vertex?
  5. Understanding Apply Dijkstra’s algorithm to find the shortest path from P to T in the network: Edges: PQ=10, PR=3, QR=4, QS=2, RS=8, RT=15, ST=5. Show each step in a table.
  6. Understanding A road network connects 6 towns (A–F). The distances (km) are: AB=12, AC=5, BD=8, BC=4, CD=7, CE=11, DE=3, EF=6, DF=9. Find the shortest driving route from A to F and its total distance.
  7. Understanding Apply Dijkstra’s algorithm starting from vertex 1 in the graph: edges 1–2=7, 1–3=9, 1–6=14, 2–3=10, 2–4=15, 3–4=11, 3–6=2, 4–5=6, 5–6=9. Find the shortest path from vertex 1 to vertex 5.
  8. Understanding In a computer network, the time (milliseconds) to transmit data between nodes is: AB=20, AC=10, BD=15, BC=25, CD=5, CE=30, DE=10. Find the fastest route from A to E and the minimum transmission time.
  9. Problem Solving A courier must travel from depot D to delivery point Z through a road network: DA=4, DB=8, AC=3, BC=6, AE=5, CE=2, BE=7, EZ=10, CZ=15. Apply Dijkstra’s algorithm to find the shortest route and its length.
  10. Problem Solving A weighted graph has 6 vertices (A–F) with edges: AB=2, AC=5, AD=1, BC=3, BD=4, CD=2, CE=7, DE=5, DF=8, EF=3.
    • (a) Find the shortest path from A to F using Dijkstra’s algorithm.
    • (b) Find the shortest path from A to E.
    • (c) Which vertex is the hardest to reach from A (has the greatest shortest-path distance)?

View Full Worked Solutions →