Theory of Computer Science

Shortest path (class P)

Dijkstra and breadth-first search on the same graph — and they disagree.

What this demo checks

Both of these are class P: the work grows politely with the size of the graph, so they finish essentially instantly at this scale and would still finish on a graph of a million nodes.

They are also solving DIFFERENT problems, which is easy to miss. Dijkstra finds the cheapest route by edge weight. Breadth-first search finds the route with the fewest hops and ignores weight entirely.

Try A to H. There is a single direct edge A–H with weight 25. BFS takes it — one hop, job done. Dijkstra refuses it and walks the long way round for a total cost of 16. Neither is wrong; they are answering different questions.

1.Pick a start node and an end node
2.Choose Dijkstra or breadth-first search
3.Press Run and watch nodes light up in the order the algorithm settles them

AlgorithmStartEnd

Loading the graph…

What the code is doing under the hood

Dijkstra keeps a priority queue of the cheapest known cost to each node, always settling the cheapest unsettled node next. BFS keeps a plain FIFO queue, which is what makes it explore in rings of equal hop count.

Swapping the queue is the entire difference between the two algorithms. Everything else — the visited set, rebuilding the path from predecessors — is the same code.

Code card

Run this demo to see the code that executed.

Travelling salesman — exact solver (NP-hard)

Try every possible tour and keep the best. Guaranteed optimal, and doomed.

What this demo checks

The problem: visit every city once and return home, by the shortest route. This solver finds the true optimum by simply trying every ordering.

The number of tours is (n−1)! — one city has 1, three cities have 2, five cities have 24. Ten cities would be 362,880. Twenty would be more tours than there are seconds in the age of the universe. That is what NP-hard means in practice.

Honestly: At 1 to 5 cities this solver is FAST — you are watching a slowed-down animation, not a struggling computer. The chart shows the shape of the growth; the explosion happens beyond the range this page allows.

1.Pick a city count: 1, 2, 3 or 5
2.Press Run
3.Watch each candidate tour get drawn and measured, with the best kept

Cities

Loading the cities…

What the code is doing under the hood

One loop over every permutation of the cities, computing each tour's length and keeping the shortest. City 0 is fixed as the start because a closed tour has no preferred starting point, which removes n identical rotations for free.

There is no cleverness here and that is the point — for this problem, nobody knows a fundamentally clever exact method.

Code card

Run this demo to see the code that executed.

Travelling salesman — heuristic solver

Always hop to the nearest unvisited city. Fast, and usually good enough.

What this demo checks

Nearest-neighbour builds exactly ONE tour: from where you are, go to the closest city you have not visited yet, and repeat. It never reconsiders.

The work is n² instead of factorial, so it stays fast at any size. The catch is that it comes with no guarantee.

At 1, 2 and 3 cities it finds the same tour as the exact solver — it looks perfect. At 5 cities it does not: its greedy first hops leave it with an expensive journey home, and its tour is about 30% longer than the optimum. That is the trade in one picture. Run both and compare the lengths.

1.Pick the same city count you used above
2.Press Run
3.Compare the tour it finds against the exact answer

Cities

Loading the cities…

What the code is doing under the hood

A loop that repeatedly picks the minimum-distance unvisited city. No search, no backtracking, no memory of alternatives.

This is the shape of most practical answers to NP-hard problems: give up on certainty, keep the speed, and measure how far off you are.

Code card

Run this demo to see the code that executed.

How runtime grows

Every point is a real measurement taken on this server, accumulated as you run the demos above. The animation pacing is never plotted — only the time the solver itself took.

Run a TSP demo to start plotting measured runtimes here.

What P, NP and NP-hard actually mean

P: Problems a computer can SOLVE quickly — the work grows as a polynomial in the input size. Shortest path is here. Doubling the graph roughly doubles or quadruples the work; it does not explode.
NP: Problems where a proposed answer can be CHECKED quickly, even if finding it might be hard. Given a tour and a budget, checking whether it fits is trivial. Everything in P is also in NP.
NP-hard: At least as hard as everything in NP. The travelling salesman problem is here. No polynomial-time exact algorithm is known for any of them, and one would immediately give you a fast algorithm for all of them.
P vs NP: Is checking an answer genuinely easier than finding one? Nobody knows. It has been open since 1971 and carries a one-million-dollar prize. Everything on this page assumes the answer is no, because that is what half a century of failing to find fast algorithms suggests — but it remains an assumption.