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

Looking at the idea of path-relaxation, our first fleeting thought is a wish to magically conjure an ordering of the edges so that relaxing them in that order would compute the $s - v$ shortest paths for all vertices $v$ in a digraph. 

Learn about a single-source shortest-paths algorithm for directed acyclic graphs.

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

An Immediate Algorithm for DAGs