Dijkstra's Algorithm Visualizer

An interactive academic tool for exploring pathfinding workflows and minimum priority queue behaviors.

Build Custom Graph

Draw custom graph topologies and verify stepwise algorithmic pathfinding solutions.

Random Graph

Generate random graphs to explore algorithm behavior under varying node densities.

Animation Player

Observe the algorithm autonomously finding the shortest paths with visual highlighting.

Quiz Mode

Test theoretical understanding. Select the optimal extracted node at each algorithm step.

Methodology Overview

Read academic literature on Dijkstra's Algorithm and the usage of O(log V) Min-Heaps.

Unvisited
In Queue
Current Node
Evaluating
Finalized
Unvisited
In Queue
Current Node
Evaluating
Finalized
Unvisited
In Queue
Current Node
Evaluating
Finalized
Unvisited
In Queue
Current Node
Evaluating
Finalized

Understanding Dijkstra's Algorithm & Min-Heaps

starting node to every other node in a graph. It works by expanding outward like a ripple in a pond. At every step, the algorithm looks at all unvisited boundary nodes and greedily chooses the one that is strictly the closest. By rigorously finalizing distances one by one in ascending order, it slowly maps the perfect path to all destinations without ever needing to guess or backtrack.

Formal Pseudocode
1) d(s) = 0, d(v) = ∞ for all v ≠ s. T = V.
2) while T is not empty:
3) u = arg min { d(v) | v ∈ T }
4) T = T \ {u}
5) for each v in Neighbors(u) AND in T:
6) d(v) = min(d(v), d(u) + weight(u,v))

Section 2: What is a Min-Heap?

A Min-Heap is a specialized binary tree designed to instantly answer one specific question: "What is the smallest number right now?". It strictly enforces the Heap Property: every parent node must be geometrically smaller than both its children. Because of this structural rule, the absolute minimum element is physically trapped at the very top (the root) of the tree at all times.

Section 3: The Integration Engine (Why O(log V)?)

To efficiently figure out which boundary node is currently the closest, Dijkstra's Algorithm utilizes a Priority Queue. If we used a standard list, searching for the smallest path would require scanning every single node, costing O(V) time per step. Instead, by integrating a Min-Heap, the engine simply pops the root. Re-stabilizing the tree after popping only requires filtering the gaps down the height of the tree. Since the tree halves at every tier, the height is O(log V). Thus, discovering and extracting the next optimal node costs only O(log V) time, accelerating massive network calculations immensely!

A0
B5
C8
D12
E15
F9
G22

Section 4: The Cycle Dilemma

Dijkstra's Algorithm easily handles Positive Cycles because traveling through them continuously strictly increases the total mathematical distance, naturally causing the Min-Heap engine to eventually reject those inflated paths. However, if Negative Cycles are injected into the grid, the algorithm's entire "Greedy Choice Property" shatters. A node previously extracted from the top of the Min-Heap—assumed fully finalized and optimal—could mathematically be sabotaged by a hidden negative loop found deeper in the graph. This paradox breaks the engine, causing it to dive into recursive infinite loops unless explicitly trapped.