Congratulations on making it all the way to the end! We covered a lot of ground in this course, and we hope that you enjoyed the journey.

Highlights and reflections

As we reach the end, let’s look at and reflect on some of the highlights from this course.

In the context of depth-first search, we saw how the order in which vertices are visited and explored during the search contains a wealth of information about the structure of the graph. We saw how to tap into this information and use it to develop some versatile applications, from finding cut-vertices in undirected graphs to finding strongly connected components in directed graphs.

We looked at shortest paths in the context of both weighted and unweighted, directed graphs. We saw some single-source shortest-paths algorithms. Such algorithms can be used for finding paths that have the smallest associated costs like smallest travel time, monetary cost, and opportunity cost. They can also be used for finding paths that maximize profits or other gains. We also saw that in order to find shortest paths between all pairs of vertices, there are better ways than blindly running a single-source algorithm from each vertex.

Final Remarks