Shortest Path Problems
Learn Dijkstra's algorithm for finding shortest paths in weighted graphs, with step-by-step examples and real-world applications in HSC Advanced Mathematics.
Weighted Graphs
A weighted graph is a graph where each edge has a numerical value (weight) associated with it. Weights can represent distances, travel times, costs, or any measurable quantity.
Vertices (nodes): Represent locations, cities, or points of interest.
Edges: Represent connections or paths between vertices.
Weights: Numerical values on edges representing distance, time, or cost.
The shortest path problem asks: what is the minimum total weight to travel from one vertex to another? This is not always the path with the fewest edges — it is the path with the smallest sum of weights.
Example: A direct route from A to D might have weight 10, but going A → B → D via two edges with weights 3 and 4 gives a total of 7, which is shorter.
We need a systematic algorithm to find the shortest path, especially in large graphs.
Dijkstra's Algorithm
Dijkstra's algorithm finds the shortest path from a single source vertex to all other vertices in a weighted graph with non-negative weights. It works by systematically visiting vertices in order of their distance from the source.
Steps of Dijkstra's Algorithm:
1. Set the distance to the source as 0 and all other vertices as ∞. Mark all vertices as unvisited.
2. Select the unvisited vertex with the smallest distance. This is the current vertex.
3. For each unvisited neighbour, calculate the distance through the current vertex. If this is less than the currently recorded distance, update it.
4. Mark the current vertex as visited.
5. Repeat steps 2-4 until all vertices are visited or the destination is reached.
Key principle: Once a vertex is marked as visited, we have found the shortest path to it. Dijkstra's algorithm is a greedy algorithm that always picks the nearest unvisited vertex.
Limitation: Dijkstra's algorithm does not work with negative edge weights.
Step-by-Step Example
Consider a graph with vertices A, B, C, D, E and edges: A–B(4), A–C(2), B–D(5), C–B(1), C–D(8), C–E(10), D–E(2). Find the shortest path from A to E.
Initial: A=0, B=∞, C=∞, D=∞, E=∞.
Visit A (dist 0): Update B=4, C=2.
Visit C (dist 2): Update B=min(4, 2+1)=3, D=min(∞, 2+8)=10, E=min(∞, 2+10)=12.
Visit B (dist 3): Update D=min(10, 3+5)=8.
Visit D (dist 8): Update E=min(12, 8+2)=10.
Visit E (dist 10): Done!
Shortest path: A → C → B → D → E
Total distance: 2 + 1 + 5 + 2 = 10
Key Vocabulary
Weighted Graph
A graph where each edge has a numerical weight representing distance, cost, or time.
Dijkstra's Algorithm
A greedy algorithm that finds the shortest path from a source to all other vertices in a graph with non-negative weights.
Greedy Algorithm
An algorithm that makes the locally optimal choice at each step, hoping to find the global optimum.
Shortest Path
The path between two vertices with the minimum total weight (not necessarily the fewest edges).
Worked Examples
Find the shortest path from S to T in a graph: S–A(3), S–B(7), A–B(2), A–T(9), B–T(4).
Step 1: S=0, A=∞, B=∞, T=∞. Visit S: A=3, B=7.
Step 2: Visit A(3): B=min(7, 3+2)=5, T=min(∞, 3+9)=12.
Step 3: Visit B(5): T=min(12, 5+4)=9.
Answer: Shortest path S → A → B → T with distance 9.
A delivery company has routes: Depot–X(5), Depot–Y(8), X–Y(2), X–Z(7), Y–Z(3). Find the shortest route from Depot to Z.
Step 1: Depot=0, X=5, Y=8. Visit Depot.
Step 2: Visit X(5): Y=min(8, 5+2)=7, Z=min(∞, 5+7)=12.
Step 3: Visit Y(7): Z=min(12, 7+3)=10.
Answer: Depot → X → Y → Z with total distance 10.
Explain why the direct edge is not always the shortest path.
Consider: A–B(10), A–C(3), C–B(4).
Direct path: A → B costs 10.
Indirect path: A → C → B costs 3 + 4 = 7.
Answer: The indirect path (7) is shorter than the direct edge (10). This is why we need an algorithm rather than simply choosing direct routes.
Knowledge Check
Select the correct answer for each question. Click "Check Answer" to see if you are right.
Question 1
In Dijkstra's algorithm, which vertex is selected next at each step?
Question 2
Given edges P–Q(6), P–R(2), R–Q(3), what is the shortest path from P to Q?
Question 3
Dijkstra's algorithm does NOT work correctly when:
Question 4
Using Dijkstra from vertex A with edges A–B(1), A–C(4), B–C(2), B–D(6), C–D(3), what is the shortest distance from A to D?
Question 5
What does "greedy" mean in the context of Dijkstra's algorithm?
Key Concepts Summary
- ● Weighted graphs assign numerical values to edges representing distance, cost, or time.
- ● Dijkstra's algorithm finds shortest paths from a source to all other vertices using a greedy approach.
- ● At each step, select the unvisited vertex with the smallest tentative distance.
- ● Dijkstra's algorithm requires non-negative edge weights.
- ● Applications include GPS navigation, network routing, and logistics planning.