CITS2200 - Lecture 23

CITS2200 - Lecture 22
Shortest Paths - Slides

A weighted graph has a value (edge weights) attached to each edge
Shortest path → minimum sum of edge weights between two vertices
- Also called distance between vertices

Dijkstra’s algorithm finds shortest path to all vertices from start vertex
- Graph must be connected, with undirected edges and non-negative edge weights
This is a greedy algorithm → optimal choice made at each step without considering what is ahead or already transpired
- ! If we have negative-weight edges, it could mess up distances for vertices already in the cloud breaking the algorithm

How does it work?

We grow a ‘cloud’ of vertices (like Prim-Jarník’s algorithm)
- Begin with starting vertex s
- Eventually cover all vertices
Store with each vertex v a label d(v) representing current known shortest path from v to s in the subgraph
- Subgraph contains cloud and adjacent vertices
At each step:
- Add to the cloud vertex u, which is outside the cloud and has the smallest distance label, d(u)
- Update the labels of vertices adjacent to u

Runs in $O (m lo g n)$ time, given we are using adjacency list structure

Consider edge e = (u,z) such that:
- u is vertex most recently added to cloud
- z is not in cloud
The relaxation of edge e updates distance d(z) as follows:
- d(z) ← $min {d (z), d (u) + weight (e)}$

Edge relaxation is used in Dijkstra’s algorithm to update our distance labels

End of Unit!

Quartz 5