Introduction

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.

Try It

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">A map of 6 towns (A–F) joined by roads; each label is the road’s length. We want a route from <b>A</b> to <b>F</b>. <b>Shortest</b> is instant. <b>Longest simple</b> (no town twice) has no shortcut — it must search.</p>
<svg id="map" viewBox="0 0 320 200" aria-label="map of towns"></svg>
<div class="status" id="status">Pick a button below.</div>
<div class="btns">
  <button id="short" type="button">Shortest path</button>
  <button id="long" type="button">Longest simple path</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Same weighted graph, two opposite questions from A to F.
//  Shortest path  -> Dijkstra (greedy, never explores most routes): in P.
//  Longest SIMPLE path (no repeated town) -> exhaustive DFS over all simple paths: NP-hard (it contains the Hamiltonian-path problem). Negating weights does NOT help because it creates negative cycles.
const NODES = ['A','B','C','D','E','F'];
const POS = { A:[30,100], B:[110,40], C:[110,160], D:[210,40], E:[210,160], F:[290,100] };
// undirected edges with lengths
const EDGES = [
  ['A','B',4],['A','C',2],['B','C',1],['B','D',5],['C','D',8],
  ['C','E',10],['D','E',2],['D','F',6],['E','F',3]
];
const adj = {}; NODES.forEach(n => adj[n] = []);
EDGES.forEach(([u,v,w]) => { adj[u].push([v,w]); adj[v].push([u,w]); });
const edgeKey = (u,v) => [u,v].sort().join('-');

function dijkstra(src, dst){
  const dist = {}, prev = {};
  NODES.forEach(n => dist[n] = Infinity); dist[src] = 0;
  const seen = new Set();
  while (seen.size < NODES.length){
    let u = null, best = Infinity;
    for (const n of NODES) if (!seen.has(n) && dist[n] < best){ best = dist[n]; u = n; }
    if (u === null) break;
    seen.add(u);
    for (const [v,w] of adj[u]) if (dist[u]+w < dist[v]){ dist[v] = dist[u]+w; prev[v] = u; }
  }
  if (dist[dst] === Infinity) return null;
  const path = []; let c = dst; while (c !== undefined){ path.unshift(c); c = prev[c]; }
  return { path, cost: dist[dst] };
}

function longestSimple(src, dst){
  let best = null, explored = 0;
  const visited = new Set();
  (function dfs(u, cost, path){
    if (u === dst){ explored++; if (!best || cost > best.cost) best = { path: path.slice(), cost }; return; }
    for (const [v,w] of adj[u]) if (!visited.has(v)){
      visited.add(v); path.push(v);
      dfs(v, cost+w, path);
      path.pop(); visited.delete(v);
    }
  })(src, 0, [src]);
  visited.add(src);
  return best ? { ...best, explored } : null;
}

const svg = document.getElementById('map');
const SVGNS = 'http://www.w3.org/2000/svg';
let onEdges = new Set(), onNodes = new Set();
function el(tag, attrs){ const e = document.createElementNS(SVGNS, tag);
  for (const k in attrs) e.setAttribute(k, attrs[k]); return e; }

function draw(){
  svg.innerHTML = '';
  EDGES.forEach(([u,v,w]) => {
    const [x1,y1] = POS[u], [x2,y2] = POS[v];
    svg.appendChild(el('line', { class:'edge'+(onEdges.has(edgeKey(u,v))?' on':''), x1,y1,x2,y2 }));
    const lab = el('text', { class:'elabel', x:(x1+x2)/2, y:(y1+y2)/2-3 });
    lab.textContent = w; svg.appendChild(lab);
  });
  NODES.forEach(n => {
    const [x,y] = POS[n];
    const g = el('g', { class:'node'+(onNodes.has(n)?' on':'') });
    g.appendChild(el('circle', { cx:x, cy:y, r:13 }));
    const t = el('text', { x, y }); t.textContent = n; g.appendChild(t);
    svg.appendChild(g);
  });
}
function highlight(path){
  onEdges = new Set(); onNodes = new Set(path);
  for (let i=0;i<path.length-1;i++) onEdges.add(edgeKey(path[i], path[i+1]));
  draw();
}
function setStatus(t, cls){ const s = document.getElementById('status'); s.textContent = t; s.className = 'status '+cls; }

document.getElementById('short').addEventListener('click', () => {
  const r = dijkstra('A','F');
  highlight(r.path);
  setStatus(fmt('Shortest A→F: %path%  (length %cost%). Dijkstra found it without trying every route.', { path: r.path.join('→'), cost: r.cost }), 'short');
  console.log('shortest', r.path.join('-'), r.cost);
});
document.getElementById('long').addEventListener('click', () => {
  const r = longestSimple('A','F');
  highlight(r.path);
  setStatus(fmt('Longest simple A→F: %path%  (length %cost%). It had to explore %explored% full routes.', { path: r.path.join('→'), cost: r.cost, explored: r.explored }), 'long');
  console.log('longest', r.path.join('-'), r.cost, 'explored', r.explored);
});
document.getElementById('reset').addEventListener('click', () => {
  onEdges = new Set(); onNodes = new Set(); draw(); setStatus('Pick a button below.', '');
});
draw();
Result
Console

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 Real Complexity

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+Vlog⁡V)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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/short-vs-long-path/Content licensed under CC BY-NC 4.0.