- Output of the Dijkstra algo is a spanning tree. We will prove that the generated tree is a MST
Proof
- By contradiction: assume the algo outputs an expensive tree
- If the algo doesn’t work, then at some point, it will reach a point where it does a mistake
- we will prove that this mistake is actually not a mistake and the ‘mistake’ is actually no worse than the optimal solution
- 30
- There must be a cycle and a green edge
- Because the algo picks an edge of least cost
- no worse than the optimal solution
- is acc better coz