The shortest route is not always the fewest steps

Shortest according to what?

In an unweighted graph, “shortest” means fewest edges. In a weighted graph, it usually means smallest sum of edge costs. The two can disagree.

Imagine edges A–B with weight 8, A–C with weight 2, and C–B with weight 3. BFS chooses A–B: one edge. The minimum-cost route is A–C–B: two edges, total cost 5. Here, a longer-looking route is cheaper.

Keep the best distance so far.

Dijkstra’s algorithm begins with distance zero at the source and infinity elsewhere. It repeatedly settles the unsettled node with the smallest tentative distance, then inspects its incident edges. Princeton’s shortest-path chapter explains the algorithm and its nonnegative-weight requirement.

For a current node u and neighbor v, relaxation asks whether distance[u] + weight(u,v) improves distance[v]. If so, save the smaller value and record u as the parent of v. The parent chain reconstructs a shortest route.

distance[source] = 0
while a reachable unsettled node remains:
  u = unsettled node with minimum distance
  settle u
  for each unsettled neighbor v of u:
    candidate = distance[u] + weight(u, v)
    if candidate < distance[v]:
      distance[v] = candidate
      parent[v] = u

Why nonnegative weights matter.

Once a node is settled, the algorithm treats its distance as final. With nonnegative edges, a later detour cannot produce a cheaper distance to that node. A negative edge breaks this reasoning. Zero-weight edges are allowed. Cornell’s shortest-path lecture develops the settled-distance argument.

This lab rejects negative weights. In an undirected graph, a negative edge is especially problematic for minimum-cost walks: traversing it back and forth creates an arbitrarily cheap walk. Shortest simple paths are a different problem.

What the implementation promises.

The lab uses a linear scan to pick the next node, giving O(V² + E) computation time. A binary heap can improve selection efficiency, but would obscure a small educational implementation. The trace stores frontier snapshots and highlights the final route after every reachable node has been processed.

Disconnected targets retain infinite distance. Multiple equally cheap routes may exist; the lab returns the first one found under its node and edge order. Decimal arithmetic uses JavaScript numbers, so tiny floating-point rounding differences are possible.