**MA618 Homework #4
Due Monday, March 1
**

**
Problems to turn in
**

**Problem (Recovering the dipaths with the Floyd-Warshall Algorithm) p.26. Suggestion: Assume the vertices are numbered from 1 to***n*=|*V*(*G*)|. Keep an extra matrix around, initially filled with 0's. Whenever the minimum in step 2 is changed to a new value, change entry (*v*,*w*) to*k*.**Problem (Minimum-weight dipaths in graphs with no dicycles) p.29. Include a proof that the bijection exists.****Problem (Knapsack program) p.29. Do part (a) only.****Exercise (Scheduling, continued) p.42.****Exercise (Intersection of three matroid polytopes) p.46.**

- Exercise (Bellman-Ford Algorithm) p.25.
- Exercise (Dijkstra's Algorithm) p.27.
- Exercise (Shortcut) p.38.

Mon Feb 22 07:50:33 EST 1999