Lesson 6: Shortest paths by trial and error
When the shortest path uses more edges
SkillShortest paths by trial and error
Worked example
Find the shortest path from to in the weighted graph, and its length.
Step 1: Spot the light and heavy edges
The light edges are , and , so good routes probably use them. The heavy edge is worth avoiding.
This is the "trial" in trial and error: aim your first tries at light edges, then check the alternatives.
Step 2: Get from A to B cheaply
Direct, – costs 4, but –– costs .
Step 3: Get from D to F cheaply
Direct, – costs 6, but –– costs .
Step 4: Compare the complete routes
- –––:
- –––:
- ––––:
- ––––:
- –––––:
The other routes use with a detour, and total 18 or more.
Step 5: State the shortest path
The shortest path is –––––, with length 13. It uses five edges, while both three-edge routes total 15.
Answer
–––––, with length 13.
Try a similar one
A fresh question of the same kind, checked as you answer, with hints and a full solution.
Method
Look for light edges and short detours that beat a heavy direct edge.
List the candidate routes and total each one.
Choose the least total, even if it uses more edges.
Watch out for
Choosing ––– because it looks the most direct. It totals 15.