Dynamic Programming: Shortest Paths Algorithms

Related lectures (51)

Focuses on open problems and the importance of reformulating problems with better tools and intuition.

Covers Dijkstra's algorithm for shortest path problems and its application in ALL-TO-ONE and ALL-PAIRS algorithms.

Covers the concept of graph sketching with a focus on connected components.

Explores the Bellman Ford algorithm for finding the shortest path in graphs with negative edge weights.

Covers the implementation and analysis of disjoint sets data structure and introduces the concept of minimum spanning trees.

Demonstrates the iterative process of applying Dijkstra's algorithm to find optimal paths.

Explores Bellman-Ford algorithm for negative weight graphs and currency exchange rates.

Explores Cheeger's inequalities for random walks on graphs and their implications.

Covers stochastic properties, network structures, models, statistics, centrality measures, and sampling methods in network data analysis.

Introduces graph theory, network flows, and flow conservation laws with practical examples and theorems.

Explains message passing in graphical models and the matching problem in graph theory.

Explores belief propagation on graphs, emphasizing normalization, recursive relations, and iterative computation of the partition function.

Explores interlacing families of polynomials and 1-sided Ramanujan graphs, focusing on their properties and construction methods.

Covers embedding graphs into trees with a focus on minimizing distortion and Bartal Tree embeddings.

Covers graphical models for probability distributions and factor graphs representation.

Explores a classic handshake problem at a party using graph representation.

Explores the Cartesian product operation on graphs and introduces the concept of cubes.

Explores distances on graphs, cut norms, spanning trees, blockmodels, metrics, norms, and ERGMs in network data analysis.

Explores expanders, Ramanujan graphs, eigenvalues, Laplacian matrices, and spectral properties.

Covers Dijkstra's algorithm and its application to the all-pairs shortest path problem.

Page 2 of 3