# Weighted Graphs

**Bart Massey**

## Edge-weighted Graphs

Extend graph with a "labeling" function l: V -> Z+ that gives the "weight" of each edge of a graph.

`SINGLE-SOURCE SHORTEST PATH Given: A connected graph (V, E). A distinguished start node v0 in V. A set G of goal nodes with G a subset of V. A positive integer weight l(e) for every e in E. Find: A path p from v0 to vg for some vg in G with the sum of edge weights along the path minimal among all paths from v0 to some vg in G.`

## Dijkstra's Algorithm (Book)

Given graph (V, E) in adjacency-list form, start node v0, goal nodes G, weight function l:E->N

`if v0 in G return S <- new empty set D <- new empty dictionary for each edge (v0, w) in E D[v0] <- l(v0, w) loop T <- keys(P) \ S if T is empty fail v <- vertex in T minimizing P[v] if v in G return insert v into S for each edge (v, w) in E D[w] <- min(D[w], D[v] + l(v, w))`

Correctness: Must terminate when every reachable node has been searched or a when a goal node is reached.

Yields right answer by triangle property: see below.

Runtime: O(n

^{2}) by outer loop, minimization loop

## Dijkstra's Algorithm ("Standard")

Given graph (V, E) in adjacency-list form, start node v0, goal nodes G, weight function l:E->N

`P <- new empty dictionary Q <- new empty priority queue S <- new empty set insert v0 into Q with priority 0 while Q is not empty: extract min priority v from Q if v in G return path extracted from P, v insert v into S for w in neighbors of v if w not in S P[w] <- v insert w into Q with priority of v + l((v, w)) fail`

Run-time: O(|E|)

Correctness: Completes when all vertices have been examined.

Soundness by contradiction. Imagine longer of two paths was selected. Now look at where the two paths converge for the final time. Must take last step of shorter path first.

## All-Pairs Shortest Path

Might want to pre-build a map showing the shortest distance from any node to any other.

Can use Dijkstra's on each source vertex to build a VxV array of inter-node distances.

Given this table, one can reconstruct the path by moving from start to some goal by looking at the shortest total path from current node to neighbors.

`v <- v0 P <- new empty sequence while v =/= g find neighbor w of v minimizing l(v, w) + D[w, g] append w to P v <- w return P`

Can also construct a VxV array of parents for faster pathing.

There's another standard way to build the VxV table.

## Floyd-Warshall Algorithm

Idea: Use intermediate nodes in some order to find shorter paths.

`D <- VxV matrix of distances, all "infinity" for (v, w) in E D[v, w] <- l(v, w) for k in V for i in V for j in V d <- G[i, k] + G[k, j] if d < G[i, j] G[i, j] <- d`

Correctness: Terminates. Every path transiting k is considered.

Running Time: O(n

^{3}), vs n calls to Dijkstra's.Variant can compute "transitive closure" of a directed graph at a vertex.