Dijkstra's Shortest Path

Watch Dijkstra's greedily relax edges to find the shortest path from the source to every reachable node.

Time: O((V+E) log V)

Space: O(V)

Uses: Min-Heap

Non-negative weights only

Start Node:

Speed: 1200ms

Step 1 of 0

Unvisited

In Heap

Current

Settled

Shortest path edge

Time:O((V+E) log V)

Space:O(V)

Data Structure:Min-Heap

Negative weights:No

Question 1 of 3

What data structure makes Dijkstra's efficient?

DSAverse

Graph Algorithms

Loading Graph Algorithms...

BFS Traversal

visited: 0 / 7