DescriptionStorage and representation of graphs (networks) on a computer. Common graph theory problems. Breadth first search algorithm. Depth first search algorithm. Dijkstra's algorithm. Topological sort algorithm. Shortest/longest path on a acyclic graph. Bellman Ford's algorithm. Floyd-Warshall all pairs shortest path algorithm. Finding bridges/articulation points. Finding strongly connected components (Tarjan's). Travelling salesman problem (TSP).
This course provides a complete introduction to Graph Theory algorithms in computer science.
Topics covered in these videos include: how to store and represent graphs on a computer; common graph theory problems seen in the wild; famous graph traversal algorithms (DFS & BFS); Dijkstra's shortest path algorithm (both the lazy and eager version); what a topological sort is, how to find one, and places it's used; learning about detecting negative cycles and finding shortest paths with the Bellman-Ford and Floyd-Warshall algorithms; discovering bridges and articulation points in graphs; understanding and detecting strongly connected components with Tarjan's algorithm, and finally solving the travelling salesman problem with dynamic programming.