How do we find the route of least total weight between two points in a network?
Find the shortest path between two vertices in a weighted network and interpret it in context.
How to find the shortest path between two vertices in a weighted network by systematic listing or labelling, interpret the result, and tell shortest path apart from minimum spanning tree.
Reviewed by: AI editorial process; not yet individually human-reviewed
Have a quick question? Jump to the Q&A page
Jump to a section
What this dot point is asking
You must find the least-weight route between two named vertices and interpret it as the cheapest, shortest or fastest journey depending on what the weights represent.
What shortest path means
In a weighted network the shortest path between two vertices is the route whose edge weights add to the smallest total. The weights may be distance, time or cost, so "shortest" can mean cheapest or fastest.
Finding the path
For the small networks in this course, two reliable methods work.
- Systematic listing. List the plausible routes from start to finish, total each one's weights, and choose the smallest.
- Labelling (forward working). Label each vertex with the least total distance from the start, building outwards; the start's label is and each other label is the smallest running total reaching it.
The labelling method in more detail
The labelling method scales better than listing when a network has many vertices. Begin by labelling the start vertex . Then, for every vertex directly reachable from a labelled vertex, work out the running total along each incoming edge and keep the smallest such total as that vertex's permanent label. Continue outward until the destination is labelled. The destination's label is the length of the shortest path, and you recover the route by tracing back through the edges that produced each label. Because each label records the least distance found so far, a vertex's label can be improved if a cheaper route to it is discovered before it is made permanent.
Interpreting the answer
State both the route and its total, in context: "the shortest path is A to C to B to D, a distance of 8 km". If two routes tie for the minimum, both are valid answers and you should say so. When the weights are times, the shortest path is the fastest journey; when they are costs, it is the cheapest, so always phrase the conclusion in the units the question uses.
Shortest path versus minimum spanning tree
These two network tasks are easily confused. A shortest path links two specific vertices at least total weight. A minimum spanning tree links every vertex at least total weight. One answers a journey question, the other a connection question.