How does Dijkstra's Algorithm work?

It maintains a set of "closest" nodes and repeatedly expands the one with the smallest known distance, relaxing its outgoing edges to update neighbors.

Does it work with negative edge weights?

No, Dijkstra's assumes that once a node is processed, its distance is final. Negative weights can break this greedy assumption.

What is the time complexity?

Using a Binary Heap (Priority Queue), it is O((V+E) log V). With a Fibonacci Heap, it can reach O(E + V log V).

Dijkstra's Algorithm

Learn the most famous algorithm for finding the shortest path from a starting node to all other nodes in a weighted graph.

Ready to start

Priority Queue (Node: Dist)
Empty

Node	Distance
No Data

Speed

See the Logic in Motion

Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.

Unlock VisualizerPREMIUM FEATURE

Intuition

Imagine finding the quickest route on a map. You always take the road that gets you to a new town in the shortest total time.

Once you're sure you've found the fastest way to a town, you use that town to find fast routes to its neighbors.

Concept

Greedy Approach: Always process the closest unvisited node next.
Relaxation: If we find a path to node V through node U that is shorter than the current known path to V, we update (relax) the distance to V.
Priority Queue: Used to efficiently select the node with the smallest tentative distance.

How it Works

Algorithm Steps:

Set distance to start node = 0, all others = ∞.
Add start node to a Priority Queue (PQ).
While PQ is not empty:
- Pop node u with the smallest distance.
- If u is already visited, skip it.
- Mark u as visited.
- For each neighbor v of u with weight w:
  - If dist[u] + w < dist[v]:
  - Update dist[v] = dist[u] + w.
  - Add v to PQ.

Step-by-Step Breakdown

Watch the visualization:

Orange Node: Currently processing (popped from PQ).
Light Orange Edge: Checking this connection for a shorter path.
Emerald Node: Visited (Shortest path guaranteed).
Node Label: Shows ID and current shortest distance (e.g., "A (0)", "B (5)").

When to Use

Use Dijkstra's when:

Finding optimal routes in GPS/Navigation systems.
Routing data packets in networks (OSPF, IS-IS).
The graph has non-negative edge weights.

When NOT to Use

Negative Edge Weights: Dijkstra's can fail with negative weights. Use Bellman-Ford instead.
Unweighted Graphs: BFS is simpler and faster (O(V+E) vs O(E log V)).

How to Identify

"Find shortest path", "Minimum cost to reach target", "Weighted positive graph".

Stop Guessing, Start Mastering.

Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.

Start Your Premium Prep