loading
loading
loading
Computer Science / Algorithms
Part of the Dijkstra's Algorithm Learning Experience →Watch single-source shortest paths get computed on a weighted graph — extract the nearest unvisited node, relax its edges, repeat.
Dijkstra's algorithm finds the shortest distance from one start node to every other node in a graph with non-negative edge weights. It keeps a distance array (0 for the start, ∞ for everywhere else) and a priority queue of unvisited nodes ordered by their current best-known distance. Each step: extract the unvisited node with the smallest distance — that distance is now final, since nothing unvisited could reach it more cheaply — then relax every edge out of it, updating a neighbor's distance whenever the path through the current node is shorter than what's currently recorded. Repeat until every reachable node is visited. This visualizer runs that exact process on a small fixed weighted graph, showing the graph, the currently relaxing edge, and every node's live distance at once.
BFS finds the fewest-edges path, which only equals the shortest path when every edge costs the same. The moment edges have different weights (as they do here), BFS's guarantee breaks — Dijkstra tracks accumulated cost instead of hop count, which is exactly what relaxation does.
Because the priority queue always extracts the smallest remaining distance, and all edge weights are non-negative — any path through a still-unvisited node would already cost at least that node's own (larger) distance, so it can never produce a shorter path to the node just extracted.
Dijkstra breaks — the 'extracted distance is final' guarantee relies on weights only being able to make paths longer, never shorter. Graphs with negative weights need the Bellman-Ford algorithm instead.