Finds the minimum-weight path between two vertices in a weighted graph.
Algorithm (informal):
1. Assign distance 0 to start vertex; $\infty$ to all others.
2. Visit the unvisited vertex with smallest current distance.
3. Update distances to its neighbours: new distance = current + edge weight (if smaller than existing).
4. Repeat until destination is reached.
Find the shortest path from A to E:
Edges (weights): A–B=4, A–C=2, B–D=5, B–E=10, C–D=1, D–E=3.
| Step | Vertex visited | Updated distances |
|---|---|---|
| Start | — | A=0, B=∞, C=∞, D=∞, E=∞ |
| 1 | A | B=4, C=2 |
| 2 | C | D=2+1=3 |
| 3 | D | B=min(4,3+5)=4, E=3+3=6 |
| 4 | B | E=min(6,4+10)=6 |
| 5 | E | Done: E=6 |
Shortest path: A → C → D → E, total weight = 6.
A spanning tree connects all $n$ vertices with $n-1$ edges and no cycles. The minimal spanning tree (MST) minimises total edge weight.
Kruskal’s Algorithm:
1. List all edges in ascending order of weight.
2. Add each edge if it does not form a cycle.
3. Stop when $n-1$ edges are added.
Edges sorted: C–D=1, A–C=2, A–B=4, B–D=5, D–E=3, B–E=10.
Add C–D=1 (no cycle). Add A–C=2 (no cycle). Add D–E=3 (no cycle). Add A–B=4 (no cycle). 4 edges for 5 vertices — done.
MST total weight = 1+2+3+4 = 10.
Used for project scheduling. Activities are vertices/edges; weights are durations.
Key concepts:
- Earliest start time (EST): earliest an activity can begin
- Latest start time (LST): latest an activity can start without delaying the project
- Float = LST − EST (slack time)
- Critical path: sequence of activities with zero float — any delay here delays the whole project
$$\text{Project minimum duration} = \text{length of critical path}$$
APPLICATION: Critical path is used in construction, events management, and IT project planning. The critical path identifies which tasks must not be delayed.
EXAM TIP: For each algorithm, show your working step by step. Kruskal’s — list edges in order. Dijkstra’s — show the distance table. Critical path — show EST and LST for each vertex and identify zero-float activities.
