Shortest PathLesson 36Free preview

DSA Dijkstra's

This lesson is part of DSA · All levels

Summary

Dijkstra looks for the shortest path from one source to all nodes on a graph with non-negative weight. This greedy algorithm always visits the node at the smallest temporary distance, then relaxes its neighbor. Using the priority queue, the complexity becomes O((V + E) log V).

Key points

Greedy: always process the smallest distance nodes
Not to be worn on the side with negative weight
Using relaxation: renew the distance when the new path is shorter
Complexity with priority queue

Full lesson

Code examples and quizzes

Full lessons, code examples, and quizzes are available to subscribers. 5 questions.