logo
SEE ALGORITHMS

Dijkstra's Algorithm Visualization

Dijkstra's Algorithm finds the shortest path from a source node to all other nodes in a graph with non-negative weights. It uses a priority queue to explore nodes in order of increasing distance. This algorithm works by maintaining a set of visited nodes and, at each step, selecting the unvisited node with the smallest known distance to visit next. This process continues until all nodes have been visited, making it essential for network routing problems.

Pseudocode

dist = map vertex -> Infinity
dist[src] = 0
heap = new MinHeap()
heap.insert(src, 0)
while heap is not empty:
    (u, d) = heap.extract()
    if u is not visited:
        relax(u, d)
function relax(u, d):
    mark u as visited
    for each neighbor v of u:
        alt = d + weight(u, v)
        if alt < dist[v]:
            dist[v] = alt
            heap.insert(v, alt)

Draw Graph

AI Summary

(5 credits)

See what happens with your input

Get a short, step-by-step explanation of this visualization. Turn on AI Summary, then start a fresh run with your input.


Common Interview Questions

Why does Dijkstra's algorithm fail or produce incorrect results on graphs with negative edge weights?

Dijkstra's algorithm makes a greedy assumption: once a node is popped from the Min-Priority Queue, its shortest distance is finalized and will never decrease. A negative edge encountered later could reveal a shorter path to an already finalized node, invalidating Dijkstra's greedy guarantee.

What is the time complexity of Dijkstra's algorithm using a Min-Heap vs an unsorted array?

Min-Heap implementation: O((V + E) log V). Unsorted Array implementation: O(V²). Array implementation is actually faster for complete/extremely dense graphs where E ≈ V², while Min-Heap excels on sparse graphs.

How is Dijkstra's algorithm adapted in real-world GPS navigation systems (e.g. Google Maps)?

Raw Dijkstra is too slow on worldwide road networks. GPS systems use A* Search with geometric heuristics, Contraction Hierarchies (CH), and Multi-Level Dijkstra to precompute highway routes and answer shortest path queries in milliseconds.


💬  Discussion

to join the discussion


Curious to Learn More?

Hand-picked resources to deepen your understanding


Learn DSA on Udemy
Learn DSA on Udemy
As an Udemy Associate, I earn from qualifying purchases.

© 2025 See Algorithms. Code licensed under MIT, content under CC BY-NC 4.0