Gain insights into key graph algorithms, including depth-first search, shortest paths, and flow networks. Explore their applications and foundational role in advanced computing disciplines.

This technology-agnostic course will teach you about many classical graph algorithms essential for a well-rounded software engineer. 

You will begin with an introduction to the running-time analysis of algorithms and the representation and structure of graphs. You’ll cover the depth-first search algorithm and its many applications, like detecting cycles, topological sorting, and identifying cut-vertices and strongly connected components. You will then cover algorithms for finding shortest paths and minimum spanning trees. You’ll also learn about the Ford-Fulkerson algorithm and its use in finding a maximum flow and minimum cut in networks. Moreover, you will adapt it to find maximum matchings and minimum vertex covers in bipartite graphs. Finally, you will learn about the Gale-Shapley algorithm for finding stable matchings.

The material in this course serves as a basis for other advanced algorithms, like parallel and distributed algorithms, and has many diverse applications in other computing disciplines.

Mastering Graph Algorithms

# Changing rational capacities to integers 

We know that the Ford-Fulkerson algorithm terminates when the graph has integer capacities. Suppose we are faced with a flow network that has rational numbers as edge capacities. To guarantee that the algorithm terminates, we would like to use the following strategy:
1. Change the rational capacities to integer values in some systematic way.
2. Run the Ford-Fulkerson algorithm to find max flow with respect to the changed capacities.
3. Recover the flow in the flow network with respect to the original rational capacities. 








Learn how to use the Ford-Fulkerson algorithm when dealing with rational edge capacities. 

Introduction

Review: Asymptotic Notation and Math Prerequisites

Working with Graphs

Depth-First Search and Applications

Prelude: Shortest Paths

Single-source Shortest Paths in Weighted Digraphs

All Pairs Shortest Paths

Minimum Spanning Tree

Flows

Matchings and Vertex Covers

Conclusion

Use Simulated Annealing for the Traveling Salesman Problem

Thought Exercise: Rational Capacities

Changing rational capacities to integers