DSA DSA In Depth
0%
From-Scratch Build

A* & Bidirectional Shortest-Path Router with Consistent Potentials

A shortest-path routing engine implementing Dijkstra, A* with admissible/consistent heuristics, and Bidirectional Dijkstra with exact stopping condition and node-expansion instrumentation.

~45 min Advanced Lessons: Build Lab: A* and Bidirectional Dijkstra Pathfinding Engine with Consistent Potentials, A* Search & Bidirectional A*: Admissibility, Consistency (Triangle Inequality) & Optimality Proof, Binary & d-ary Heaps: Floyd's O(N) Bottom-Up Build-Heap Proof, Depth-First Search: Parenthesis Theorem, White-Path Theorem & Tree/Back/Forward/Cross Edges, Negative Weights: Bellman-Ford, Negative Cycle Reconstruction & Systems of Difference Constraints, All-Pairs Shortest Paths: Floyd-Warshall DP Transitive Closure & Johnson's Potential Reweighting
Interactive Build Lab 0/4 Steps Completed

Code & Verify in the Browser Workbench

Complete 4 progressive engineering steps in JavaScript or TypeScript against an in-browser Node.js v22 runtime (virtual filesystem, loopback TCP/HTTP, and automated unit tests) — zero local setup required.

A Search as Johnson's Potential Reweighting

In A\ search, prioritizing vertices by $f(u) = g(u) + h(u)$ is algebraically equivalent to running Dijkstra's algorithm on reduced edge weights:

$$w_h(u, v) = w(u, v) - h(u) + h(v)$$

  • Consistency (Monotonicity): $h(u) \le w(u, v) + h(v) \iff w_h(u, v) \ge 0$. Because reduced edge weights are non-negative, every vertex popped from the priority queue has finalized its optimal $g(u)$ on the very first pop.
  • Admissibility: $h(u) \le d(u, t)$ with $h(t) = 0$.

The Bidirectional Stopping Criterion Trap

A common bug in bidirectional Dijkstra is stopping as soon as a vertex $v$ is scanned by both the forward and backward searches. That vertex $v$ is guaranteed to have been reached by both frontiers, not* to lie on the global shortest path!

Instead, we maintain $\mu = \min_{(u,v) \in E} (\text{dist}_F[u] + w(u,v) + \text{dist}_B[v])$ across all relaxed edges touching the opposite frontier, and terminate only when the two frontier radii satisfy:

$$\min_{x \in Q_F} \text{dist}_F[x] + \min_{y \in Q_B} \text{dist}_B[y] \ge \mu$$

Curriculum Connections

Guided Implementation Walkthrough (4 Progressive Steps)

Step 1: Admissible & Consistent Euclidean Heuristic

  • Core Mechanical Concept: Admissible & Consistent Euclidean Heuristic
  • Target Module: index.js (Step1)
  • Engineering Specification: Implement heuristic(u, target) using Math.hypot(dx, dy). When edge weights are $\ge$ Euclidean distance, $h(u) \le w(u,v) + h(v)$ (triangle inequality / consistency), guaranteeing that nodes popped from the PQ never need re-expansion.
  • Verification Invariant: verifies Step 1: Admissible & Consistent Euclidean Heuristic

Step 2: A Priority Search

  • Core Mechanical Concept: A Priority Search
  • Target Module: index.js (Step2)
  • Engineering Specification: Implement astar(source, target) prioritizing nodes by $f(u) = g(u) + h(u, t)$ and reconstructing the shortest path upon popping target.
  • Verification Invariant: verifies Step 2: A Priority Search

Step 3: Bidirectional Frontier Alternation

  • Core Mechanical Concept: Bidirectional Frontier Alternation
  • Target Module: index.js (Step3)
  • Engineering Specification: Maintain distF on adj from source and distB on revAdj from target, always expanding whichever frontier has the smaller top priority.
  • Verification Invariant: verifies Step 3: Bidirectional Frontier Alternation

Step 4: Exact Mu-Stopping Criterion & Path Splice

  • Core Mechanical Concept: Exact Mu-Stopping Criterion & Path Splice
  • Target Module: index.js (Step4)
  • Engineering Specification: Track the best seen s-t bridge mu = Math.min(mu, distF[u] + w + distB[v]). Do NOT stop at the first shared node; terminate only when pqF.peekPriority() + pqB.peekPriority() >= mu.
  • Verification Invariant: verifies Step 4: Exact Mu-Stopping Criterion & Path Splice

Asymptotic & Memory Layout Guarantees

  • Category: Graph Algorithms
  • Difficulty: Advanced (~45 minutes)
  • Key Architectural Highlights:
    • Admissible & consistent Euclidean/Octile heuristic guiding A     frontier expansion
    • Bidirectional search with exact mu-stopping criterion (topF + topB >= bestPathLen)
    • Node-expansion telemetry comparing standard Dijkstra, A*, and Bidirectional search on the same graph
  • Tags & Primitives: A* Search, Bidirectional Dijkstra, Admissible Heuristic, Consistent Potential, Shortest Path

Production Systems Context & Verification

This from-scratch implementation is engineered with zero external dependencies and deterministic verification harnesses. Every internal invariant—from pointer restoration and bitmask addressing to amortized potential bounds and tree height balance—is asserted directly in test.js. Use the interactive browser workbench above to complete the guided steps in Guided Lab mode or inspect and benchmark the complete reference architecture in Full Solution mode.