Concept

Shortest path problem

Related lectures (29)

Ising Model: 2D Expansion

Explores the Ising model in 2D, emphasizing system expansion and properties.

Shortest Path: Properties of the Algorithm

Explains the properties of the shortest path algorithm and how to find the shortest path in a network.

Shortest Path Problems: Bellman-Ford

Explores solving shortest path problems with the Bellman-Ford algorithm and negative cost cycles.

Dijkstra's Algorithm: All-Pairs

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

Shortest Paths: Negative Weights

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

Shortest Path in Directed Graphs

Covers finding the shortest path in directed graphs efficiently using algorithmic approaches and discussing related NP-complete problems.

Shortest path, Longest path

Explores the implications of transforming a shortest path problem into a longest path problem in optimization.

Transhipment and Shortest Paths

Covers optimality conditions, total unimodularity, and algorithms for transhipment problems.

Shortest Path: Introduction

Covers one-to-one shortest path, negative cost edges, and optimal solutions.

Fixed Points in Graph Theory

Focuses on fixed points in graph theory and their implications in algorithms and analysis.

Dijkstra's Algorithm and Shortest Path

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

Bellman Ford Algorithm

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

Lagrangian Duality: Optimization Tutorial

Covers Lagrangian duality in optimization, focusing on the minimum bin path problem and path time optimization.

Algorithmic Paradigms for Dynamic Graph Problems

Covers algorithmic paradigms for dynamic graph problems, including dynamic connectivity, expander decomposition, and local clustering, breaking barriers in k-vertex connectivity problems.

Shortest Paths: Negative Weights & Applications

Covers Minimum Spanning Trees, Kruskal's Algorithm, and Shortest Paths in directed graphs.

Dynamic Programming: Shortest Paths Algorithms

Explores dynamic programming strategies for finding shortest paths in networks with various algorithms and complexities.

Fundamental Groups

Explores fundamental groups, homotopy classes, and coverings in connected manifolds.

Networks: Paths

Explains paths in networks, including simple paths and cycles.

Shortest Paths: Bellman-Ford and Dijkstra

Covers the Bellman-Ford and Dijkstra algorithms for finding shortest paths in graphs with different edge weights.

Optimization of Pseudometrics in Graphs

Covers the optimization of pseudometrics in graphs, focusing on minimizing pseudometrics and the shortest path metric.