Dijkstra, Bellman–Ford and Floyd–Warshall: comparison

The same graph, different questions

Every edge is directed and has the same weight in all three models. Dijkstra and Bellman–Ford compute distances from the selected source to every reachable vertex. Unlike the earlier target-only Dijkstra demo, this comparison continues after settling the selected destination. A different target selects another answer in that source row.

Floyd–Warshall computes a whole matrix independently of the selected source and destination. The repeated row in its panel is the row for the selected source, so it can be compared directly with the other two panels. The full matrix remains visible: changing to D → A shows that direction matters.

Each vertex denotes the same object in every panel. Colors identify algorithms, not a speed ranking: blue is Dijkstra, amber is Bellman–Ford, purple is Floyd–Warshall. Colored graph lanes show currently reconstructible routes for the selected pair; rings show the vertices associated with the completed stage. Use the highlight selector to isolate one algorithm.

What one animation tick means

Dijkstra settles vertices in order of their smallest known distance. Vertices settled at the same distance are grouped into one visual stage, including zero-weight discoveries at that distance. It uses a linear scan of the frontier, not a binary heap. Once a vertex is settled, this implementation does not reopen it.

Bellman–Ford scans the entire edge list on each pass. A relaxation replaces d(v) when d(u) + w(u,v) is smaller. The implementation updates distances in place: an improvement can be used again later in the same pass. The player shows the complete pass at once, then a cycle check and the final affected-vertex classification. A pass with no improvements finishes the algorithm early.

Floyd–Warshall allows one more intermediate vertex k and applies d(i,j) = min(d(i,j), d(i,k) + d(k,j)) to every pair. Every update in one stage reads the same previous matrix; independent changes appear together. The final stages inspect the diagonal and mark affected pairs.

A tick advances one stage of each algorithm that has not finished. These stages contain different amounts of work. Animation duration, tick count, and edge versus pair counters are not a benchmark. Finished panels keep their final result while the other algorithms continue.

Dijkstra counts examined outgoing edges of settled vertices. Bellman–Ford counts edge examinations in relaxation passes and the control pass; affected-vertex propagation is not included in this counter. Floyd–Warshall counts V² pair checks per intermediate vertex, including unreachable pairs. These are different kinds of operations.

Nonnegative example: 10 → 9 → 7

The direct A → D edge costs 10. A → B → D costs 3 + 6 = 9. A → B → C → D costs 3 + 2 + 2 = 7, and all three algorithms return 7 for A → D. Their intermediate estimates differ because they propagate improvements in different orders.

The edge order is deliberately reversed for Bellman–Ford. Its first pass finds B = 3 and D = 10; the next pass finds C = 5 and D = 9; the third improves D to 7. Dijkstra settles A, B, C, D. Floyd–Warshall first improves A → D via B, then via C.

When all weights equal one, minimum cost equals minimum edge count. Here the direct A → D edge costs 1 and beats the three-edge alternative. In general equal-cost routes can differ: the demo preserves the first strictly best route rather than minimizing the number of edges among ties.

A negative edge changes which algorithm applies

Set B → C to −2, or choose the negative-edge example. There is still no negative cycle. Bellman–Ford and Floyd–Warshall return A → B → C → D with cost 3 + (−2) + 2 = 3.

Dijkstra is not run and does not display a guessed answer. A later negative edge can improve a vertex that was already settled, invalidating the rule used by this implementation. The validator rejects a negative edge anywhere in the graph, including a disconnected component. This is a deliberate contract; it does not mean every graph with a negative edge would necessarily produce an incorrect number.

For a counterexample, use edges A → B = 1, A → C = 2, C → B = −3. Settling B at 1 before visiting C misses the better cost −1 when settled vertices cannot be reopened. A lucky correct answer on another negative graph would not establish the algorithm's guarantee.

A negative cycle does not invalidate every answer

Add C → B = 1. The cycle B → C → B costs −2 + 1 = −1. A can reach it and it can reach D, so A → D has no finite minimum. Bellman–Ford marks affected destinations from A; Floyd–Warshall marks each pair that can pass through such a cycle. Both show −∞ for A → D. Finite intermediate values before classification are provisional, not shortest-path answers.

Choose D → D on that graph. D cannot reach the cycle, so its zero-cost empty route remains valid. D → A remains unreachable (∞). A negative cycle only makes a pair unbounded when the source can reach it and the cycle can reach the destination.

The disconnected-cycle example adds E with a negative self-loop. From A, Bellman–Ford still returns A → D = 3 and cannot discover that cycle. Floyd–Warshall sees E → E = −∞ in its full matrix while A → D remains 3. Selecting E as the source makes Bellman–Ford detect the cycle too. Dijkstra stays unavailable because of its whole-graph nonnegative-weight contract.

Work, memory and choosing an algorithm

V is the number of vertices and E the number of directed edges. The table describes the implementations in this player. Dijkstra's frontier is scanned linearly, giving O(V² + E) time; a binary heap version commonly uses O((V + E) log V). Dijkstra and Bellman–Ford store graph copies and linear source arrays, using O(V + E) working memory. Their distance output is O(V).

Bellman–Ford takes O(VE + V) time in the worst case, including initialization and marking vertices reachable from an improving edge. This is commonly written O(VE) for nonempty graphs. Floyd–Warshall takes O(V³) time and O(V²) working memory, including its next-hop and reachability matrices. Its output is a full O(V²) matrix.

Animation snapshots are extra memory, excluded from those algorithm bounds. The retained matrix stages require O(V³) storage; preparing detailed Bellman–Ford snapshots can temporarily require O(V²E). The interactive input is limited to six vertices, at most 32 unique directed pairs and integer weights from −99 to 99. A rejected edit or damaged shared link keeps the current valid run.

For one source with nonnegative weights, start with Dijkstra. With negative edges, Bellman–Ford provides source distances and reachable-cycle classification. When many different source–destination queries are needed on a sufficiently small graph, consider Floyd–Warshall. Running a single-source algorithm once is not the same workload as solving every pair.

How the comparison reuses the existing models

The player does not replace the three algorithms with a separate simulation. The code below calls the same tested models as the individual articles. It runs Dijkstra with directed adjacency and complete-source mode, compares Bellman–Ford's row with the corresponding matrix row, and uses null to signal that Dijkstra's precondition is not met. The imports refer to this website's data modules.

The comparison groups real snapshots into complete visual stages. Sharing saves the graph, source, destination, highlight, paused tick and speed on a clean player page. Video export records the same states from the beginning with the selected speed and highlight, without narration or music.

import { createFloydInput, floydWarshallSteps } from "./floyd-warshall";
import { dijkstraSteps } from "./dijkstra";
import { bellmanFordSteps } from "./bellman-ford";

function compareShortestPaths(graph, start, target) {
  const input = createFloydInput({ graph, start, target });
  const dijkstra = graph.edges.every(e => e.weight >= 0)
    ? dijkstraSteps(graph, start, target, {
        directed: true, allTargets: true
      }).at(-1).state.distance
    : null;
  const bellmanFord = bellmanFordSteps(input).at(-1).state.distance;
  const floydWarshall = floydWarshallSteps(input).at(-1).state.distance;
  return {
    dijkstra,
    bellmanFord,
    floydWarshall,
    selected: {
      dijkstra: dijkstra?.[target] ?? null,
      bellmanFord: bellmanFord[target],
      floydWarshall: floydWarshall[start][target]
    }
  };
}