The shortest path by inspection practice questions | General Mathematics (Year 11, VCE Units 1 & 2, Graphs and networks, Weighted graphs and shortest paths)

Q: What is a shortest path?

It is a path between two named vertices whose total edge weight is as small as possible among the available paths

Q: Why are repeated vertices usually left out when routes are compared?

A repeated vertex creates a detour in a positive-weight network. The inspection method compares sensible routes without repeated vertices or edges

Q: Why is choosing the cheapest next edge not enough?

A locally cheap edge can force expensive later edges. A shortest-path decision requires comparing complete route totals

Q: Can I use a calculator?

A calculator is allowed unless a question is marked no calculator

Q: Which year level and chapter is this?

Year 11, VCE Units 1 & 2, General Mathematics, chapter 8: Graphs and networks

Finding a shortest path by inspection

To find a shortest path, list sensible routes between the named vertices. Add every route's weights and compare the complete totals

\text{route total}=\text{sum of edge weights}

List sensible routes Use routes without repeated vertices or edges and leave out obvious detours \(\displaystyle A\mathord{-}B\mathord{-}D,\quad A\mathord{-}C\mathord{-}D\)
Total each route Add the weight of every edge in a complete route \(\displaystyle 7+6+10=23\,\text{km}\)
Compare complete totals The smallest total identifies the shortest path among the routes considered \(\displaystyle 23\,\text{km}<29\,\text{km}\)
Do not count edges only The number of edges is not the same as the total weight \(\displaystyle A\mathord{-}D:18\,\text{km},\quad A\mathord{-}B\mathord{-}C\mathord{-}D:12+3+2=17\,\text{km}\)

Worked example

A network of walking tracks has two sensible routes from M to T. Route 1 has consecutive legs of 8 km and 9 km. Route 2 has consecutive legs of 5 km, 6 km and 10 km. Find the shortest route by inspection

\text{Route 1: }M\mathord{-}N\mathord{-}T\quad 8+9;\qquad \text{Route 2: }M\mathord{-}P\mathord{-}Q\mathord{-}T\quad 5+6+10

\(\displaystyle 8+9=17\,\text{km}\)Route 1 has a total length of 17 km
\(\displaystyle 5+6+10=21\,\text{km}\)Route 2 has a total length of 21 km
\(\displaystyle 17\,\text{km}<21\,\text{km}\)Compare the complete route totals
\(\displaystyle M\mathord{-}N\mathord{-}T,\quad 17\,\text{km}\)Route 1 is the shortest route and its length is 17 km

Common mistakes

Choosing by fewest edges

✕\(\displaystyle A\mathord{-}D:20\,\text{km}\Rightarrow\text{shortest}\)✓\(\displaystyle A\mathord{-}B\mathord{-}C\mathord{-}D:7+6+5=18\,\text{km}<20\,\text{km}\)

The route with fewer edges can still have a larger total, so complete route totals must be compared

Using a greedy next edge

✕\(\displaystyle 3+12+4=19\,\text{km}\)✓\(\displaystyle 8+7=15\,\text{km}<19\,\text{km}\)

The cheapest available next edge can lead to an expensive route, so compare complete routes instead

Leaving out a route leg

✕\(\displaystyle 5+6=11\,\text{km}\)✓\(\displaystyle 5+6+10=21\,\text{km}\)

Every edge in the stated route must be included once when its total is calculated

Difficulty levels

introCompare complete route totals with a direct edge on a five-vertex network

standardTotal three named candidate routes and compare their lengths

challengeEnumerate sensible routes and report the shortest total without named candidates

examSelect the shortest total from computed fewest-edge, greedy, omitted-leg and near-miss values

Questions about this topic

What is a shortest path?+

It is a path between two named vertices whose total edge weight is as small as possible among the available paths

Why are repeated vertices usually left out when routes are compared?+

A repeated vertex creates a detour in a positive-weight network. The inspection method compares sensible routes without repeated vertices or edges

Why is choosing the cheapest next edge not enough?+

A locally cheap edge can force expensive later edges. A shortest-path decision requires comparing complete route totals

Can I use a calculator?+

A calculator is allowed unless a question is marked no calculator

Which year level and chapter is this?+

Year 11, VCE Units 1 & 2, General Mathematics, chapter 8: Graphs and networks

In this chapter

Count the vertices, edges and loops of a graph Degrees, the degree sum, and even and odd vertices Connected graphs and bridges Identify isomorphic graphs Planar graphs and drawings in planar form Faces and Euler's formula 8C Euler's formula: A full network investigation Classify a route: walk, trail, path, circuit or cycle Eulerian trails and circuits: existence and identification 8E Eulerian trails and circuits: A full network investigation Hamiltonian paths and cycles Read a weighted graph The shortest path by inspection 8G Weighted graphs and shortest paths: A full network investigation Trees and spanning trees Minimum spanning trees by Prim's and Kruskal's algorithms 8H Trees and minimum spanning trees: A full network investigation