IE 411: Graphs and Network Flows (Python)
Miscellaneous Handouts and Course Information
Lecture Slides
- Introduction
- Introduction to Python
- Lecture 1: Graphs and Network Flows
- Lecture 2: Data Structures
- Lecture 3: Implementation and Empirical Analysis
- Lecture 4: Theoretical Analysis and Complexity
- Lecture 5: Depth-first Search
- Lecture 6: General Graph Search
- Lecture 7: Minimum Spanning Trees
- Lecture 8: Shortest Path Problems
- Lecture 9: Dijkstra’s Algorithm
- Lecture 10: General Label-Correcting Algorithm
- Lecture 11: All-Pairs Shortest Path Algorithms
- Lecture 12: The Maximum Flow Problem
- Lecture 13: Augmenting Path Algorithms
- Lecture 14: Shortest Augmenting Path Algorithm
- Lecture 15: Preflow-push Algorithm
- Lecture 16: Minimum Cost Network Flows
- Lecture 17: Primal-Dual Algorithms
- Lecture 18: Spanning Tree Solutions
- Lecture 19: Network Simplex Algorithm
- Lecture 20: Sensitivity Analysis
- Lecture 21: Matching and Matroids
- Lecture 22: Lagrangian Relaxation
- Lecture 23: Multicommodity Flow Problems
Assignments
Reference Texts
- Course Text: Algorithms in C++ (Part 5): Graph Algorithms by Robert Sedgewick.
On-line Reference
- Similar course at Berkeley with good pointers to additional material.
Course Software
Python Links
If you find something here useful, buy me a beer!
