Dijkstra Shortest Path Simulation

Dijkstra's algorithm finds minimum-cost paths from a source node in weighted graphs with non-negative edge costs by greedily expanding the closest unvisited node and relaxing neighbor edges.

Interactive simulation

Current node
-
Visited
0 / 6
Max cost (F)
0
Selected edge
none
Speed
1x

Legend

  • Unvisited (∞ initially)
  • Discovered / Frontier
  • Active node being expanded
  • Finalized shortest path
  • Selected edge (click Block Edge)
  • Blocked link

Event log

    How to use this simulation

    1. Press Relax Next once to step through one edge relaxation at a time, or press Resume to animate continuously from the chosen Source Node.
    2. Click any edge line in the graph to select it, then press Block Edge to cut that link and watch shortest paths reroute.
    3. Use Step to advance one event, Slower (down to 0.25x) and Faster (up to 4x) to control animation speed, and Reset to restore all edges.

    1. Greedy selection of the closest unvisited node

    At each step, Dijkstra picks the unvisited node with the smallest tentative distance from the source. Because all edge weights are non-negative, once a node is chosen as the minimum among unvisited nodes, no shorter path to it can arrive later.

    2. Edge relaxation

    When expanding node u with cost dist[u], the algorithm checks each outgoing edge (u, v) of weight w. If dist[u] + w < dist[v], it updates dist[v] = dist[u] + w and records u as v's predecessor along the shortest tree.

    3. Why non-negative weights are required

    Dijkstra assumes adding another edge never decreases total path cost. If a graph has negative edge weights, an already-finalized node could later see a lower cost, requiring Bellman-Ford instead.

    Algorithm properties

    AspectDetailWhy It Matters
    Edge weight ruleNon-negative weights (w ≥ 0)Preserves greedy optimality once a node is finalized
    Relaxation conditiondist[u] + w < dist[v]Updates neighbor cost only when a cheaper route is found
    Time complexityO((V + E) log V) with min-heapScales cleanly to sparse and dense graphs

    Key takeaways

    • Always expand the unvisited node with the smallest current distance from the source.
    • Relaxing an edge tests whether going through the current node improves a neighbor's cost.
    • Blocking an edge forces remaining paths to use alternative routes or increases path cost.

    Related topics

    Go-Back-N

    Sliding window ARQ with cumulative ACKs.

    Selective Repeat

    Sliding window ARQ with individual ACKs and buffering.

    Bellman-Ford

    Shortest paths with negative edge weights.

    Coming soon

    A* Search

    Heuristic-guided shortest path search.

    Coming soon