Held: Wednesday, 11 November 2015

Back to Outline 29 - Shortest Paths. On to Outline 31 - Network Flows.

Summary

We continue our exploration of shortest path algorithms.

Related Pages

Overview

• All-pairs shortest path, continued.
• The Floyd-Warshall algorithm.
• Looking ahead: The max-flow problem / Augmenting paths.

Administrivia

• 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

All Pairs Shortest Path, Continued

Reminder: The Floyd-Warshall algorithm makes a sequence of matrices, matrix k is the matrix which gives shortest paths involving only intermediate nodes numbered 0..k.

Question: How do we construct matrix k+1 from matrix k?

Question: Will this work with negative edges (but no negative cycles)?

The Max-Flow Problem

Problem: Given a weighted directed graph and two nodes (source and target), find the maximum "flow" from the source to the target, where we think of the weight of each edge as the capacity of that edge. (This is a good simplified networking problem.)

We typically build a separate flow graph from the weighted directed graph.

Augmenting Paths

Most Max-Flow algorithms work with what is called an augmenting path. That's a path from the source to the target in which each edge weight is positive.

Here's an incorrect algorithm for building a max-flow graph

while an augmenting path exists from source to target
  find the lowest edge weight on that augmenting path
  decrement each edge in the path in the original graph by that amount
  increment each corresponding edge in the flow graph by that amount

We'll do an example.

Why is the algorithm incorrect?