Shortest Path (HSC SSCE Mathematics Standard): Revision Notes
Shortest Path
What is a shortest path?
In a network, the shortest path between two points is the route where the total of all the edge weights is as small as possible. Finding shortest paths is incredibly useful in real life.
When the weights represent time, you can find the quickest route to travel. When the weights represent distance, you can find the route that covers the least distance. However, be careful - the shortest distance is not always the fastest route!
Speed Limits Matter!
If the shortest distance route has a speed limit of km/h but another route has a speed limit of km/h, the shortest distance path might actually take longer. In such cases, it's better to redraw your network using time as the edge weights instead of distance.
Definition
Shortest Path Definition
The shortest path between two vertices in a network is the path where the sum of the weights of its edges is minimised.
In other words, when you add up all the numbers on the edges you travel along, the total should be the smallest possible value.
Method of inspection
While there are advanced algorithms for finding shortest paths, the method of inspection is a straightforward approach that involves:
- Listing all reasonable paths between the two vertices
- Calculating the total weight for each path
- Comparing the totals to identify the smallest
Key Points to Remember:
- There can be more than one shortest path between two vertices (multiple paths might have the same minimum weight)
- The shortest path might not go through all vertices in the network
- You can save time by eliminating obviously inefficient routes (for example, paths that "go the long way around")
Example 11: Finding the shortest path by inspection
Worked Example: Finding the Shortest Path Between Towns
Problem: Find the shortest path between Town C and Town F.
Solution:
Step 1: Identify all likely shortest routes between Town C and Town F, then calculate their lengths.
Tip: Save time by eliminating routes that take the long way around. For example, when going from Town B to Town D, ignore routes via Town A as they're longer.
- km
- km
- km
Step 2: Compare the path lengths and identify the shortest path.
The shortest path is with a length of km.
Example 12: Finding the length of the shortest path
Worked Example: Multiple Shortest Path Calculations
Problem: Find the length of the shortest path between the following vertices:
a) and
b) and
c) and
d) and
Solution:
Part a) and :
- Identify the shortest path:
- Add the edge weights:
The shortest path from to has length .
Part b) and :
- Identify the shortest path:
- Add the edge weights:
The shortest path from to has length .
Part c) and :
- Identify the shortest path:
- Add the edge weights:
The shortest path from to has length .
Part d) and :
- Identify the shortest path:
- Add the edge weights:
The shortest path from to has length .
Example 13: Solving a shortest path problem
Worked Example: Real-World Application - Home to Shops
Problem: Darcy has drawn a network diagram representing streets from his home to the shops. The numbers indicate times in minutes. Describe the shortest path and minimum travelling time.
Step 1: Identify all likely shortest routes and calculate their lengths.
- minutes
- minutes
- minutes
- minutes
Step 2: Compare all path lengths to find the shortest.
Notice that three different paths all took minutes, but one path took only minutes.
Step 3: State your answer clearly.
The shortest path is and the minimum travelling time is minutes.
Why Check All Routes?
This example demonstrates why it's crucial to check all reasonable routes - don't just guess which looks shortest! Three paths tied at minutes, but a careful check revealed an even better path at minutes.
Summary
Key Points to Remember:
- The shortest path has the smallest total when you add up all the edge weights along that route
- Always list multiple possible paths and compare their totals - don't just guess which looks shortest
- The shortest distance path isn't always the quickest in terms of time (consider speed limits)
- There can be multiple shortest paths with the same minimum total weight
- The shortest path doesn't need to visit every vertex in the network
- Eliminate obviously inefficient routes to save time in your calculations