Graphs with numbers, called weights, attached to each edge
Often restricted to non-negative
Directed or undirected
Examples
Distance between cities
Cost of flight between airports
Time to send a message between routers
Weighted graphs
Adjacency matrix representation
T[i,j]=⎩⎪⎪⎨⎪⎪⎧wi,j∞0if i,j are connectedif i=j are not connectedif i=j
Similarly for adjacency lists
Example weighted graph
Example weighted graph
Adjacency matrix
Shortest paths
The length of a path is the sum of the weights
of its edges
Very common problem
find the shortest path from s to d
Examples
Shortest route between cities
Cheapest connecting flight
Fastest network route
…
Shortest path from vertex 1 to vertex 5
Shortest path problem
Two main variants:
Single sources
Find the shortest path from s to each node
Dijkstra's algorithm
Only for non-negative weights (important!)
All-pairs
Find the shortest path between all pairs s,d
Floyd-Warshall algorithm
Any weights
Dijkstra's algorithm
Main ideas:
Keep a set W of visited nodes
Start with W={s} (or W={})
Keep a matrix Δ[u]
Minimum distance from s to upassing only throughW
Start with Δ[u]=T[s,u](or Δ[s]=0,Δ[u]=∞)
At each step we enlargeW by adding a new vertexw∈W
w is the one with minumumΔ[w]
Dijkstra's algorithm
Main ideas:
Adding w to W might affect Δ[u]
For some neighbouru of w
We might now have a shorter path to upassing throughw
Of the form s→…→w→u
If Δ[u]>Δ[w]+T[w,u]
In this case we update Δ
Δ[u]=Δ[w]+T[w,u]
Example graph
Expanding the vertex set w in stages
Expanding the vertex set w in stages
Expanding the vertex set w in stages
Expanding the vertex set w in stages
Expanding the vertex set w in stages
Expanding the vertex set w in stages
Expanding the vertex set w in stages
Expanding the vertex set w in stages
Expanding the vertex set w in stages
Expanding the vertex set w in stages
Expanding the vertex set w in stages
Dijkstra's algorithm in pseudocode
// Δεδομένα
src : αρχικόςκόμβοςdest : τελικόςκόμβος// Πληροφορίες που κρατάμε για κάθε κόμβο v
W[u] :1ανο u είναιστοσύνολο W, 0διαφορετικά
dist[u] :οπίνακαςΔ
prev[u] :οπροηγούμενοςτου v στοβέλτιστομονοπάτι// Αρχικοποίηση: W={} (εναλλακτικά μπορούμε και W={src})
for each vertex u in Graph
dist[u] = INT_MAX // infinity
prev[u] =NULL
W[u] =0
dist[src] =0
Dijkstra's algorithm in pseudocode
// Κυρίως αλγόριθμος
whiletrue
w = vertex with minimum dist[w], among those with W[w] =0
W[w] =1if w == dest
stop
// optimal cost = dist[dest]
// optimal path = dest <- prev[dest] <- ... <- src (inverse)
for each neighbor u of w
if W[u] ==1continue
alt = dist[w] + weight(w,u) // κόστος του src -> ... -> w -> u
if alt < dist[u] // καλύτερο από πριν, update
dist[u] = alt
prev[u] = w
Using a priority queue
Finding the w∈W with minumumΔ[w] is slow
O(n) time
But we can use a priority queue for this!
We only keep vertices w∈W in the queue
They are compared based on their Δ[w]
(each w has “priority” Δ[w])
Careful when Δ[w] is modified!
Either use a priority queue that allows updates
Or insert multiple copies of each w with different priorities
the queue might contain already visited vertices: ignore them
Dijkstra's algorithm with priority queue
// Δεδομένα
src : αρχικόςκόμβοςdest : τελικόςκόμβος// Πληροφορίες που κρατάμε για κάθε κόμβο u
W[u] :1ανο v είναιστοσύνολο W, 0διαφορετικά
dist[u] :οπίνακαςΔ
prev[u] :οπροηγούμενοςτου v στοβέλτιστομονοπάτιpq : Priority queue, εισάγουμε tuples {u,dist[u]}
συγκρίνονταιμεβάσητο dist[u]
// Αρχικοποίηση: W={} (εναλλακτικά μπορούμε και W={src})
prev[src] =NULL
dist[src] =0
pqueue_insert(pq, {src,0}) // dist[src] = 0
Dijkstra's algorithm with priority queue
// Κυρίως αλγόριθμος
while pq is not empty
w = pqueue_max(pq) // w with minimal dist[u]
pqueue_remove_max(pq)
if exists(W[w]) // το w μπορεί να υπάρχει πολλές φορές στην ουρά (αν
continue// δεν κάνουμε replace), και να είναι ήδη visited
W[w] =1if w == dest
stop // optimal cost/path same as before
for each neighbor u of w
if exists(W[u])
continue
alt = dist[w] + weight(w,u) // cost of src->...->w->u
if!exists(dist[u]) OR alt < dist[u]
dist[u] = alt
prev[u] = w
pqueue_insert(pq, {u,alt}) // προαιρετικά: replace αν υπάρχει ήδη!
stop // pq άδειασε πριν βρούμε το dest => δεν υπάρχει μονοπάτι
Notation
s→d
Direct step step from s to d
sWd
Multiple steps s→…→d
All intermediate steps belong to the set W⊆V
sWd
Shortest path among all sWd
So sVd is the overall shortest one
Proof of correctness
We need to prove that Δ[u] is the minimum distance to u
after the algorithm finishes
But it's much easier to reason step by step
we need a property that holds at every step
this is called an invariant (property that never changes)
Proof of correctness
Invariant of Dijkstra's algorithm
Δ[u] is the cost of the shortest path passing only through W
And the shortest overall when u∈W
Formally:
For all u∈V the path sWu has cost Δ[u]
For all u∈W the path sVu has cost Δ[u]
Proof: induction on the size of W, for both (1), (2) together
Proof of correctness
Base case W={s}
Trivial, the only path sWu is the direct one s→u
For (1): its cost is exactly T[s,u]=Δ[u]
initial value of Δ[u]
For (2): the only u∈W is s itself
Proof of correctness
Inductive case
Assume ∣W∣=k and (1),(2) hold
The algorithm
Updates W, adding a new vertex w∈W
Updates Δ[u] for all neighbours u of w
Let W’,Δ′ be the values after the update
Show that (1),(2) still hold for W’,Δ′
Proof of correctness
We start showing that (2) still holds for W’,Δ′
The interesting vertex is the w we just added
Vertices u=w are trivial from the induction hypothesis
Show: sVw has cost Δ’[w]
Note: Δ’[w]=Δ[w] (we do not update Δ[w])
We already know that sWw has cost Δ[w] (ind. hyp)
So we just need to prove that there is no better path outsideW
Proof of correctness
Assuming such path exists, let r be its first vertex outside W
So the path sWrVw has cost c<Δ[w]
So the path sWr has cost at most c<Δ[w] (no negative weights!)
So Δ[r]<Δ[w]
Impossible! We chose w to be the one with min Δ[w]
Proof of correctness
It remains to show (1) for W’,Δ′
Take some arbitrary u
Let c be the cost of sW’u
Show: c=Δ’[u]
Three cases for the optimal path sW’u
Case 1: the path does not pass through w
So it is of the form sWu
This path has cost Δ[u] (induction hypothesis)
No update: Δ’[u]=Δ[u]=c
Proof of correctness
Case 2: w is right before u
So the path is of the form sWw→u
The cost of sWw is Δ[w] (induction hypothesis)
So c=Δ[w]+T[w,u]
So the algorithm will set Δ’[u]=Δ[w]+T[w,u]
when updating the neighbours of w
So c=Δ’[u]
Proof of correctness
Case 3: some other x appears after w in the path
So the path is of the form sWw→xWu
But the path sWw→x is no shorter than sWx
From the induction hypothesis for x∈W
So sWx→u is also optimal, reducing to case 1!
Complexity
Without a priority queue:
Initialization stage: loop over vectices: O(n)
The while-loop adds one vertex every time: n iterations
Finding the new vertex loops over vertices: O(n)
same for updating the neighbours
So total O(n2) time
Complexity
With a priority queue:
Initialization stage: loop over vectices, so O(n)
Count the number of updates (steps in the inner loop)
Once for every neighbour of every node: e total
Each update is O(logn) (at most n elements in the queue)
Total O(elogn)
Assuming a connected graph (e≥n)
And an implementation using adjacency lists
Only good for sparse graphs!
But O(nlogn) can be hugely better than O(n2)
The all-pairs shortest path problem
Find the shortest path between all pairs s,d
Floyd-Warshall algorithm
Any weights
Even negative
But no negative loops (why?)
The all-pairs shortest path problem
Main idea
At each step we compute the shortest path through a subset of vertices
Similarly to W in Dijkstra
But now the set at step k is Wk={1,…,k}
Vectices are numbered in any order
Step k: the cost of iWkj is Ak[i,j]
Similar to Δ in Dijstra (but for all pairsi,j of nodes)
Floyd-Warshall algorithm
The algorithm at each step computes Ak from Ak−1
Initial step k=0
Start with A0[i,j]=T[i,j]
Only direct paths are allowed
Floyd-Warshall algorithm
k-th iteration: the optimal iWkj either passes thorughk or not.
Ak[i,j]=min{Ak−1[i,j]Ak−1[i,k]+Ak−1[k,j]
Floyd-Warshall algorithm in pseudocode
voidfloyd_warshall() {
for (int i =0; i <= size-1; i++)
for (int j =0; j <= size-1; j++)
A[i][j] = weight(i, j)
for (int i =0; i <= size-1; i++)
A[i][i] =0;
for (int k =0; k <= size-1; k++)
// Compute A_k from A_{k-1}
for (int i =0; i <= size-1; i++)
for (int j =0; j <= size-1; j++)
if (A[i][k] + A[k][j] < A[i][j])
A[i][j] = A[i][k] + A[k][j]
}
A is the currentAk at every step k.
Complexity
Three simple loops of n steps
So O(n3)
Not better than n executions of Dijkstra in complexity
But much simpler
Often faster in practice
And works for negative weights
Readings
T. A. Standish. Data Structures , Algorithms and Software Principles in
C. Chapter 10
A. V. Aho, J. E. Hopcroft and J. D. Ullman. Data Structures and
Algorithms. Chapters 6 and 7