What this shows
Dijkstra's Algorithm and the Bellman-Ford Algorithm computing shortest paths from a single source node on the same weighted, directed graph — with the running distance table visible at every step, not just the final answer. Pick a target node to see the actual shortest path reconstructed and highlighted, or leave it on "None" to watch every node's distance converge at once.
Turn on negative weights and watch Dijkstra get it wrong
Dijkstra's Algorithm is greedy: once a node's shortest distance is finalized, the algorithm never revisits it, on the assumption that no later discovery could possibly produce something cheaper. That assumption only holds if every edge weight is non-negative. Check "Allow negative weights" and Dijkstra will sometimes finalize a node early, only for a strongly negative edge discovered later to reveal a genuinely cheaper path — one Dijkstra will never go back and find. Bellman-Ford, run on the exact same graph, gets it right, because it relaxes every edge repeatedly instead of trusting an early decision. When the two disagree, Bellman-Ford is always the correct one.
This isn't a rare edge case dug up for effect — it's the textbook reason Dijkstra is documented as requiring non-negative weights, and it's exactly what "requires non-negative weights" means in practice: not a crash, not a warning, just a silently wrong answer.
Why the graph is directed, and why some edges look doubled
Shortest-path weights are direction-specific in general — a one-way street, a flight with a different price each way, a dependency that only resolves one direction. Every connection in the graph's spanning structure is generated as two independent directed edges (A→B and B→A, each with its own random weight) specifically so any node can be chosen as the source and still reach every other node — that's why pairs of nodes often show two parallel edges with different weights and arrowheads pointing opposite ways.
What the colors mean
- Amber — a node with a known but not-yet-finalized ("tentative") distance, or the edge currently being relaxed.
- Emerald — a node whose shortest distance is finalized (Dijkstra) or confirmed at the end of the run (Bellman-Ford).
- Sky blue — the reconstructed shortest path, once a target is selected.
- Violet / sky dashed ring — the source and target nodes.
FAQ
Why does Bellman-Ford take so many more steps?
It relaxes every edge, once per pass, for up to V − 1 passes, regardless of whether a node's distance has already settled — that's the O(V · E) in its complexity, versus Dijkstra's O(V²) here (using the simple array-based version, the same one described in Algorithm Complexity Explained). The extra work is exactly what buys Bellman-Ford its correctness with negative weights.
What happens with a negative cycle?
Shortest paths through a negative cycle are undefined — you could loop the cycle forever and the total cost would keep dropping. Bellman-Ford detects this case directly (if an edge can still relax after V − 1 passes, a negative cycle is reachable from the source) and reports it rather than returning a wrong number. This tool's graph generator specifically avoids ever producing one, so you won't see this in normal use — but the detection logic is real and tested against a deliberate negative cycle.
How is this different from Graph Traversal Visualizer?
Graph Traversal Visualizer (BFS/DFS) answers "which nodes are reachable, and in what order do we discover them" on an unweighted graph — BFS happens to find the shortest path by edge count as a side effect, but it never deals with weights. This tool answers a different question — the actual minimum-cost path on a graph where every edge has a real cost.
Is anything I do here sent anywhere?
No — every calculation runs entirely in your browser. Nothing here is ever sent to a server.