# 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(n2) 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(n3), vs n calls to Dijkstra's.

• Variant can compute "transitive closure" of a directed graph at a vertex.