Weighted Graph Algorithms

Andy Novocin

Problem of the day

Oops, sorry.

Math Problem of day

(Nice version) Given the sequence 3, 2, 1, 3, 10, 23 predict the next term.

(Hard version) Given the sequence 2, 1, 3, 10, 23 predict the next term.

How do you generalize?

Strongly connected components

In directed graphs, can detect if connected by traversal and again by traversal of the reverse graph.

To spit out the components is a bit trickier.

Concept of algo

Any cycle must be in a strongly connected component (SCC)

Collapse the cycles into one 'vertex'

CROSS edges from unlabeled components into old components also create a cycle.

Repeat until no cycles.

<weighted-graphs>

First we had trees

Then graphs

Now weighted graphs

It's all about the benjamins

Minimum Spanning Trees

You have to connect a set of vertices.

Each possible edge has a cost (length of wire, travel time, political capital spent, etc)

Make the connections at the cheapest cost

BFS and DFS

Both create a tree out of a graph.

How many edges are in those trees?

If all edges have the same cost (e.g. 1) then any spanning tree is minimal.

Key concepts to spot

Greedy algorithms sometimes work

Graph cuts are useful

Trees don't create much wiggle room.

Generic MST

A = []
while !G.is_spanned_by(A):
  (u,v) = G.find_safe_edge(A)
  A.addEdge((u,v))
return A

A is "safe" if it is a subset of some MST

Graph Cuts

For \(G = (V, E)\) then any two set partition of \(V\) is called a cut: \( (S, V-S) \).

A cut respects \(A \subset E\) if no edge in \(A\) crosses the cut (has an end in \(S\) and an end in \(V-S\)).

A safeness condition

For \(A \subseteq E\) and \(A\) "safe", let \((S, V-S)\) be any cut which respects \(A\) and let \( (u,v) \in E\) be a minimal-cost edge crossing \( (S, V-S)\). Then \(A \cup (u,v) \) is safe.

Quasi-proof of safeness condition

Let \(T\) be an MST containing \(A\) but not \( (u,v)\).

There must be a path from \( u\) to \(v\) in \(T\) and it must contain an edge crossing \(S\) and \(V-S\), call that edge \((x, y)\).

The weight, \( w(x,y) \geq w(u,v) \), and \(T - (x,y) + (u,v)\) is also a spanning tree with cost no larger than \(T\).

Prim's Algorithm

Is a special case of the generic algorithm where the cut is just:

Vertices collected so far as \(S\) and the other vertices (as \(V-S\)).

The edges in \(A\) always form a single tree.

Greedy?

This approach is greedy because each new edge is the cheapest edge which expands the single tree.

Prim Code

for v in G.V {
  v.key = MAXINT;
  v.parent = null; }
root.key = 0;
A = [];
PQ = new PriorityQueue(G.V);
while PQ.notEmpty() {
  u = PQ.extract-min();
  A.push(u);
  for v in u.nbrs {
    if v in PQ && v.key > weight(u,v) {
      v.key = weight(u,v);
      v.parent = u; } } }
      

Difference with pseudo-version

Have to "find safe edge" fast.

Uses Priority Queue and clever updating

Cost depends on data structure (again)