Overview

• Preliminaries.
  • Admin.
  • Upcoming Work.
  • Extra Credit.
  • Questions.
• All-pairs shortest path, continued.
• The Floyd-Warshall algorithm.
• The max-flow problem.
• Augmenting paths.
• The Ford-Fulkerson algorithm.
• Bipartite matching.

Preliminaries

Admin

• Homework due Friday
  • Implement the naive version of the algorithm described in Section 6-2 and determine the average distance the arm travels on sets of 10, 20, and 40 random inputs in where each coordinate is between 0 and 99.
  • Implement the clever version of the algorithm described in Section 6-2.
  • Do problems 6-1, 6-5, 6-6, 6-12.
• Homework due next Wednesday (hopefully for real)
  • 6-20, 6-21, 6-23, 6-24, 6-25
• I got the example wrong. See Monday's eboard for a successful use of a promotion to get additional value.

Extra Credit

Academic

• Any other Long-String event (e.g., Friday night concert)
• Innovation Talk Wednesday.
• CS Extras Thursday: Mobile Sensing (UIowa).
• CS Table Tuesday: Something Positive

Peer

• SH concert 8:30 on Thursday
• 7 day film challenge 7:30 p.m. Friday in the Wall Theatre
• Orchestra concert 7:30 p.m. Saturday

Questions

All-pairs shortest path, continued

Make a matrix of all minimum-path lengths between two vertices.

Negative edge weights permitted, no negative cycles.

The Floyd-Warshall algorithm

Build a series of matrices. Matrix k gives shortest paths involving only intermediate nodes numbered 1 .. k.

How do we build matrix k+1 from matrix k?

  for (i = 1 to n)
    for (j = 1 to n)
      M(k+1)[i,j] = min(M(k)[i,k] + M(k)[k,j], M(k)[i,j])

What's the algorithm?

for (k = 1 to n)
  for (i = 1 to n)
    for (j = 1 to n)
      M(k+1)[i,j] = min(M(k)[i,k] + M(k)[k,j], M(k)[i,j])

Why?

• Easy to implement - Likely to get right.
• Moderately fast O(n^3)
• Works with negative edge weights

The max-flow problem

Treat the graph as a network. Edges are capacities.

Give a source and a target, find the maximum "flow" from the source to the target.

Augmenting paths

Find a path from source to target. (augmenting path) Find the smallest size of an edge on that path For each edge on that path Decrement the edge in the original graph Increment the corresponding edge in the flow graph

INCORRECT!

The Ford-Fulkerson algorithm

Bipartite matching