# Weighted graphs

K08 Δομές Δεδομένων και Τεχνικές Προγραμματισμού

Κώστας Χατζηκοκολάκης

## Weighted graphs

• 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] = \begin{cases} w_{i,j} & \text{if } i,j\text{ are connected} \\ \infty & \text{if } i\neq j\text{ are not connected} \\ 0 & \text{if } i = j \end{cases}$$
• Similarly for adjacency lists

## 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 problem

Two main variants:

• Single source $s$
• 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\}$ $\quad$ (or $W = \{\}$)
• Keep a matrix $\Delta[u]$
• Minimum distance from $s$ to $u$ passing only through $W$
• Start with $\Delta[u] = T[s,u]$ $\quad$(or $\Delta[s] = 0, \Delta[u] = \infty$)
• At each step we enlarge $W$ by adding a new vertex $w \not\in W$
• $w$ is the one with minumum $\Delta[w]$

### Dijkstra's algorithm

Main ideas:

• Adding $w$ to $W$ might affect $\Delta[u]$
• For some neighbour $u$ of $w$
• We might now have a shorter path to $u$ passing through $w$
• Of the form $s \to\ldots\to w \to u$
• If $\Delta[u] > \Delta[w] + T[w,u]$
• In this case we update $\Delta$
• $\Delta[u] = \Delta[w] + T[w,u]$

## 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

// Κυρίως αλγόριθμος
while true
w = vertex with minimum dist[w], among those with W[w] = 0

W[w] = 1
if w == dest
stop
// optimal cost = dist[dest]
// optimal path = dest <- prev[dest] <- ... <- src (inverse)

for each neighbor u of w
if W[u] == 1
continue
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\not\in W$ with minumum $\Delta[w]$ is slow
• $O(n)$ time
• But we can use a priority queue for this!
• We only keep vertices $w\not\in W$ in the queue
• They are compared based on their $\Delta[w]$
(each $w$ has “priority” $\Delta[w]$)
• Careful when $\Delta[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] = 1
if 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\to d$
• Direct step step from $s$ to $d$
• $s \xrightarrow{W} d$
• Multiple steps $s \to \ldots \to d$
• All intermediate steps belong to the set $W\subseteq V$
• $s \xRightarrow{W} d$
• Shortest path among all $s \xrightarrow{W} d$
• So $s \xRightarrow{V} d$ is the overall shortest one

## Proof of correctness

• We need to prove that $\Delta[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

• $\Delta[u]$ is the cost of the shortest path passing only through $W$
• And the shortest overall when $u\in W$

Formally:

1. For all $u\in V\;$ the path $s\xRightarrow{W} u$ has cost $\Delta[u]$

2. For all $u \in W$ the path $s\xRightarrow{V} u$ has cost $\Delta[u]$

Proof: induction on the size of $W$, for both (1), (2) together

## Proof of correctness

Base case $W = \{ s\}$

• Trivial, the only path $s \xrightarrow{W} u$ is the direct one $s\to u$
• For (1): its cost is exactly $T[s,u] = \Delta[u]$
• initial value of $\Delta[u]$
• For (2): the only $u\in 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\not\in W$
• Updates $\Delta[u]$ for all neighbours $u$ of $w$
• Let $W’,\Delta'$ be the values after the update
• Show that (1),(2) still hold for $W’,\Delta'$

## Proof of correctness

We start showing that (2) still holds for $W’,\Delta'$

• The interesting vertex is the $w$ we just added
• Vertices $u \neq w$ are trivial from the induction hypothesis
• Show: $s\xRightarrow{V} w$ has cost $\Delta’[w]$
• Note: $\Delta’[w] = \Delta[w]$ (we do not update $\Delta[w]$)
• We already know that $s\xRightarrow{W} w$ has cost $\Delta[w]$ (ind. hyp)
• So we just need to prove that there is no better path outside $W$

## Proof of correctness

• Assuming such path exists, let $r$ be its first vertex outside $W$
• So the path $s \xRightarrow{W} r \xRightarrow{V} w$ has cost $c < \Delta[w]$
• So the path $s \xRightarrow{W} r$ has cost at most $c < \Delta[w]$ (no negative weights!)
• So $\Delta[r] < \Delta[w]$
• Impossible! We chose $w$ to be the one with min $\Delta[w]$

## Proof of correctness

It remains to show (1) for $W’,\Delta'$

• Take some arbitrary $u$
• Let $c$ be the cost of $s \xRightarrow{W’} u$
• Show: $c=\Delta’[u]$
• Three cases for the optimal path $s \xRightarrow{W’} u$
• Case 1: the path does not pass through $w$
• So it is of the form $s \xRightarrow{W} u$
• This path has cost $\Delta[u]$ (induction hypothesis)
• No update: $\Delta’[u] = \Delta[u] = c$

## Proof of correctness

• Case 2: $w$ is right before $u$
• So the path is of the form $s \xRightarrow{W} w \to u$
• The cost of $s \xRightarrow{W} w$ is $\Delta[w]$ (induction hypothesis)
• So $c = \Delta[w] + T[w,u]$
• So the algorithm will set $\Delta’[u] = \Delta[w] + T[w,u]$
when updating the neighbours of $w$
• So $c = \Delta’[u]$

## Proof of correctness

• Case 3: some other $x$ appears after $w$ in the path
• So the path is of the form $s \xRightarrow{W} w \to x \xRightarrow{W} u$
• But the path $s \xRightarrow{W} w \to x$ is no shorter than $s \xRightarrow{W} x$
• From the induction hypothesis for $x \in W$
• So $s \xRightarrow{W} x \to 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(n^2)$ 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(\log n)$ (at most $n$ elements in the queue)
• Total $O(e\log n)$
• Assuming a connected graph ($e \ge n$)
• And an implementation using adjacency lists
• Only good for sparse graphs!
• But $O(n\log n)$ can be hugely better than $O(n^2)$

## 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 $W_k = \{ 1,\ldots, k\}$
• Vectices are numbered in any order
• Step $k$: the cost of $i \xRightarrow{W_k} j$ is $A_k[i,j]$
• Similar to $\Delta$ in Dijstra (but for all pairs $i,j$ of nodes)

## Floyd-Warshall algorithm

• The algorithm at each step computes $A_k$ from $A_{k-1}$
• Initial step $k=0$
• Start with $A_0[i,j] = T[i,j]$
• Only direct paths are allowed

## Floyd-Warshall algorithm

$k$-th iteration: the optimal $i \xRightarrow{W_k} j$ either passes thorugh $k$ or not. $$A_k[i,j] = \min \begin{cases} A_{k-1}[i,j] \\ A_{k-1}[i,k] + A_{k-1}[k,j] \end{cases}$$

## Floyd-Warshall algorithm in pseudocode

void floyd_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 current $A_k$ at every step $k$.

## Complexity

• Three simple loops of $n$ steps
• So $O(n^3)$
• Not better than $n$ executions of Dijkstra in complexity
• But much simpler
• Often faster in practice
• And works for negative weights