Edge-Weighted DAGs

Course video 22 of 66

In this lecture we study shortest-paths problems. We begin by analyzing some basic properties of shortest paths and a generic algorithm for the problem. We introduce and analyze Dijkstra's algorithm for shortest-paths problems with nonnegative weights. Next, we consider an even faster algorithm for DAGs, which works even if the weights are negative. We conclude with the Bellman−Ford−Moore algorithm for edge-weighted digraphs with no negative cycles. We also consider applications ranging from content-aware fill to arbitrage.

Acerca de Coursera

Cursos, programas especializados y títulos en línea impartidos por los principales instructores de las mejores universidades e instituciones educativas del mundo.

Join a community of 40 million learners from around the world
Earn a skill-based course certificate to apply your knowledge
Gain confidence in your skills and further your career