Shortest vs Longest Path

Every day your phone answers a famously hard-sounding question without breaking a sweat: what is the shortest way from here to there? Millions of roads, instant answer. The math behind it has been settled for decades.

Now flip a single word. Ask instead for the longest route between two towns that never visits the same town twice. It sounds just as reasonable — a road trip that squeezes in as many places as possible without doubling back. But this version doesn't have a fast answer at all. The very same map that gave up its shortest route in a blink will defeat every known algorithm once it grows.

That gap is one of the cleanest illustrations in all of computer science: shortest is easy, longest is brutally hard, and the reason is not about effort — it's about the structure of the problem itself.

Below is a small map of towns connected by roads, each road labelled with its length. We want a route from A to F. Press Shortest path and you get the answer instantly. Then press Longest simple path — the longest route from A to F that never repeats a town.

<p class="hint">{{hint}}</p>
<svg id="map" viewBox="0 0 320 200" aria-label="{{map_aria}}"></svg>
<div class="status" id="status">{{pick_btn}}</div>
<div class="btns">
  <button id="short" type="button">{{btn_short}}</button>
  <button id="long" type="button">{{btn_long}}</button>
  <button id="reset" type="button" class="ghost">{{btn_clear}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
#map { width: 100%; max-width: 420px; height: auto; display: block; margin: .3rem 0; }
.edge { stroke: #adb5bd; stroke-width: 2; }
.edge.on { stroke: #1d3557; stroke-width: 4; }
.elabel { font: 600 11px ui-monospace, monospace; fill: #6c757d; }
.node circle { fill: #e8eef3; stroke: #1d3557; stroke-width: 2; }
.node.on circle { fill: #1d3557; }
.node text { font: 700 13px system-ui; fill: #1d3557; text-anchor: middle; dominant-baseline: central; }
.node.on text { fill: #fff; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.short { color: #0a7d33; }
.status.long { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Notice the asymmetry. Shortest uses a smart, fast method that never has to look at most routes. Longest simple has no such shortcut: to be sure it found the maximum, it must essentially try every route that doesn't repeat a town. The counter shows how many paths it explored. Add a few more towns and that number explodes — this is the wall behind problems like the Traveling Salesman tour.

The two questions look like mirror images, but they live on opposite sides of the great divide.

• Shortest path is in P. With non-negative weights, Dijkstra's algorithm (Edsger W. Dijkstra, 1959) finds the shortest route in roughly $O(E + V \log V)$ time. Even with negative edges, Bellman–Ford solves it in polynomial time. This is a solved problem.
• Longest simple path is NP-hard. "Simple" means no repeated vertices. The catch: if a graph has a path from A to F visiting every vertex, that is a Hamiltonian path — a classic NP-complete problem. Finding the longest simple path would let you detect Hamiltonian paths, so the longest-path problem is at least as hard. No polynomial algorithm is known, and one would imply P = NP.
• Why not just negate the weights? A natural trick: multiply every length by −1 and run a shortest-path algorithm. It fails. Negative weights create negative cycles, and "shortest" then loops forever to drive the cost down. Dijkstra breaks outright, and Bellman–Ford only reports that no shortest path exists. The "no repeated vertex" rule is exactly what stops the looping — and exactly what makes the problem hard.

So the difference isn't the size of the map. It's that "shortest" has a structure greedy/dynamic methods can exploit, while "longest simple" hides the Hamiltonian-path needle in a haystack of routes.

This easy/hard pair is everywhere once you look:

• Navigation and networks: GPS routing and internet packet routing are shortest-path problems — fast and solved at planetary scale.
• Project scheduling: the critical path of a project is a longest-path computation. It stays easy only because project graphs have no cycles (they're DAGs); on general graphs the same question becomes NP-hard.
• Circuit and chip layout: the longest signal path sets the clock speed, and squeezing it is a hard optimization.
• Biology and games: snake-like "visit as much as possible" routes and DNA fragment assembly lean on long-path / Hamiltonian-style reasoning.

The lesson generalizes: a small change in what you ask for can move a problem from "instant" to "hopeless." The same jump shows up in the Traveling Salesman tour and underlies the whole P vs NP question.

Two questions, one map, a single word apart — yet they sit on opposite shores of computation. Shortest path is a triumph of clean algorithms: fast, reliable, everywhere. Longest simple path is a trapdoor into the NP-hard world, because hidden inside it is the Hamiltonian-path problem, and no clever weight trick escapes it.

The next time your phone routes you in an instant, remember its quiet twin. Ask for the longest trip that never repeats a town and you've stumbled onto a genuine instance of P vs NP — proof that in computation, the opposite of an easy question is not always an easy question.