Lesson 6: Shortest paths by trial and error

When the shortest path uses more edges

SkillShortest paths by trial and error

Worked example

  • Complex familiar

Find the shortest path from AA to FF in the weighted graph, and its length.

1 of 5 steps
  1. Step 1: Spot the light and heavy edges

    The light edges are BC=1BC = 1, AC=2AC = 2 and DE=2DE = 2, so good routes probably use them. The heavy edge CE=10CE = 10 is worth avoiding.

Try a similar one

A fresh question of the same kind, checked as you answer, with hints and a full solution.

Method

  1. Look for light edges and short detours that beat a heavy direct edge.

  2. List the candidate routes and total each one.

  3. Choose the least total, even if it uses more edges.

Watch out for

  • Choosing AA–BB–DD–FF because it looks the most direct. It totals 15.

Save your progress with a free account