Shortest Path and Pathfinding Algorithms Questions

Algorithms for finding shortest or optimal paths in graphs and grids, with emphasis on algorithm selection, correctness, and complexity. Include Dijkstra for non negative weighted graphs, Bellman Ford for graphs with possible negative edges and negative cycle detection, A Star search with admissible heuristics for informed pathfinding in grids and game maps, bidirectional search for speed improvements, and path reconstruction techniques. Cover differences between shortest path in unweighted versus weighted graphs, trade offs of heuristic design in A Star, typical grid and maze problem formulations, and practical applications such as game pathfinding, routing, and navigation.

MediumTechnical

48 practiced

You are building pathfinding for a strategy game with bridges, water penalties, and variable terrain costs. How would you design heuristics for A* that balance admissibility and informative power? Discuss approximations, hierarchical heuristics, and practical trade-offs when strict optimality is not required.

Sample Answer

Start by clarifying what “admissible” means here: a heuristic must never overestimate true remaining cost to guarantee optimality. In practice for a strategy game with bridges, water penalties and variable terrain, pure optimality is often unnecessary; we should instead aim for heuristics that are admissible when needed and highly informative otherwise.

Design ideas:

- Baseline admissible heuristic: use Euclidean (or Manhattan) distance multiplied by the minimum possible per-tile cost in the map (min_cost). This guarantees admissibility: h(p) = dist(p, goal) * min_cost. It’s cheap but weak when min_cost is much smaller than typical costs (e.g., many water tiles).

- Bridge & special-terrain awareness (admissible approximation): incorporate constrained shortest-path lower bounds: compute min_cost_per_edge conditional on necessary transitions. For example, if any path must cross at least one bridge or water region, use a slightly higher lower bound derived from topology analysis (still a lower bound). You can precompute for regions whether a bridge crossing is unavoidable and bump min_cost for nodes in that region.

- Landmark / ALT heuristics: precompute distances from a small set of landmark nodes using exact Dijkstra on the weighted graph; heuristic is max(|dist(landmark, goal) - dist(landmark, node)|). These are admissible and often much more informative than straight-line * min_cost.

- Hierarchical heuristics: build a coarse navigation graph (regions, bridge nodes). Run A* on the coarse graph to get optimistic (coarse) cost-to-go, then refine locally. Use coarse-level shortest-path cost as a heuristic for fine-level search — ensure coarse costs are computed with the same or lower-per-edge costs to remain admissible, or accept slight inadmissibility if you use weighted A*.

- Practical trade-offs when strict optimality not required: - Weighted A* (f = g + w*h, w>1) gives faster paths with bounded suboptimality. Choose w to balance speed vs quality. - Allow controlled inadmissibility: use more informative heuristics (e.g., learned value networks, CNN on map patches) that predict remaining cost but can overestimate; pair with occasional repair or local smoothing to remove pathological outcomes. - Anytime algorithms: run a fast, possibly inadmissible planner to get a good path quickly, then continue improving if time allows.

- Learning-based heuristic hybrid: train a small model to predict residual cost above a cheap admissible baseline (i.e., learn r = true_cost - baseline_h; clamp predictions to >=0). Adding predicted residual to the baseline preserves admissibility if you enforce non-negativity and cap at empirical lower bounds; relaxing caps yields faster search but non-optimal.

- Engineering considerations: - Precompute region-level distances and landmarks offline to amortize cost. - Cache and reuse heuristics for similar goals. - Monitor failure modes: bridges that become congested or dynamic terrain require replanning; prefer incremental search (D* Lite) or local repairs. - Profile: prefer heuristics that reduce node expansions per CPU constraints even if slightly more memory is used.

Summary: start with admissible, cheap heuristics (min_cost*distance), add landmarks and hierarchical coarse graphs for informativeness, and when strict optimality isn't required use weighted A*, anytime refinement, or learned residuals to speed search while keeping path quality acceptable.

MediumTechnical

48 practiced

Compare Theta-star, Jump Point Search (JPS), and standard A* on uniform-cost grids. Explain how each algorithm modifies expansions, when each yields speedups, how optimality is affected, and relative implementation complexity. Give examples of map topologies favoring each algorithm.

Sample Answer

Situation: We're comparing three pathfinding methods on uniform-cost grids: standard A*, Theta* (any-angle A* variant), and Jump Point Search (JPS).

Approach & how expansions are modified:- A*: Expands nodes on the 4- or 8-neighbor grid normally; each neighbor gets tentative g/h updates. It guarantees optimal shortest-path under the grid cost model.- Theta*: Keeps the A* search framework but, when relaxing a neighbor, tries a line-of-sight check from the current node’s parent to the neighbor; if visible it relaxes via the parent (skipping intermediate grid turning points). This reduces number of intermediate expansions by allowing “shortcut” edges.- JPS: Transforms expansion by pruning symmetric neighbors and “jumping” along directions to forced-neighbor or goal nodes. Instead of stepping every cell along straight corridors, it leaps to relevant turning points, dramatically reducing expanded nodes in open areas.

When each yields speedups:- Theta*: Best when open areas allow long unobstructed straight-line shortcuts — fewer expansions and shorter paths (geometrically closer to true Euclidean shortest path).- JPS: Best on uniform, regular obstacle layouts (long straight corridors, large open areas) where symmetry pruning and jumping skip many nodes.- A*: Baseline; competitive on highly cluttered or irregular maps where line-of-sight/jump opportunities are rare.

Optimality effect:- A*: Optimal w.r.t. grid graph (with admissible h).- Theta*: If using visible parent relaxation with Euclidean distance and admissible heuristic, it is usually optimal for Euclidean shortest path? Practically, basic Theta* is not guaranteed to produce provably optimal Euclidean shortest paths in all cases (it’s typically near-optimal); some Theta* variants (e.g., Lazy Theta*) still not strictly optimal. So Theta* trades strict optimality for any-angle improvement.- JPS: Preserves A*’s optimality on the underlying grid graph because pruning preserves shortest-path equivalence; path length equals A*’s grid-optimal path (not Euclidean-any-angle unless post-smoothed).

Implementation complexity:- A*: Simple to implement; well-known, robust.- Theta*: Moderate complexity — need robust line-of-sight checks and parent management; careful to maintain consistency of g-values.- JPS: Higher complexity — requires directional jumping logic, forced-neighbor detection, and correctness proofs; more engineering but high payoff on regular grids.

Map topology examples:- Open field with sparse obstacles: Theta* and JPS both speed up; Theta* yields smoother, shorter paths.- Long straight corridors / mazes with axis-aligned passages: JPS excels by jumping to corridor ends.- Highly cluttered, small-room maps with irregular obstacles: A* may be competitive; Theta* line-of-sight rarely applies, JPS pruning limited.

Takeaway: Use A* for simplicity and guaranteed grid-optimality; use Theta* when path smoothness and fewer turns matter and some loss of provable optimality is acceptable; use JPS when grid is regular and performance matters — it preserves optimality on the grid while greatly reducing expansions.

HardSystem Design

64 practiced

For a graph with 1 billion nodes and edges distributed across many machines, propose a design to compute shortest paths or answer many point-to-point queries. Compare frameworks (Pregel/BSP, GraphX, Giraph), algorithms (parallel Dijkstra, delta-stepping), partitioning strategies, and how you would handle stragglers and machine failures.

Sample Answer

Requirements & constraints:- Graph: ~1B nodes, edges distributed; many P2P shortest-path queries (low latency) and/or batch single-source computations. Need fault tolerance, elastic scaling, memory limits per machine, and integration with ML pipelines (feature extraction, embeddings).

High-level architecture:- Storage: distributed edge store (e.g., HDFS/Colossus or cloud object store) + partitioned in-memory graph cache (RAM on cluster nodes). Metadata service for partition map.- Compute: hybrid system: bulk synchronous for batch analytics and an async task layer for low-latency queries. Use RPC frontends to route queries to subgraph workers; results may run multi-hop coordination.

Framework comparison:- Pregel/BSP (Giraph): good for large-batch graph algorithms (convergence guarantees), easy fault recovery via superstep checkpoints. Latency high for many small P2P queries.- GraphX (Spark): convenient for integration with ML on Spark; higher GC/serialization overhead; better when mixing graph ops and ML pipelines.- Giraph: mature Pregel implementation in Hadoop ecosystem; scalable but heavyweight.Recommendation: Use BSP-based cluster (Giraph or a managed Pregel-like service) for large-scale batch builds (e.g., compute distances/landmarks, embeddings). For many point-to-point low-latency queries, build an online service using asynchronous delta-stepping or multi-source bounded search on partitioned subgraphs with caching.

Algorithms:- Parallel Dijkstra: accurate but synchronization-heavy and poor parallelism for large-degree nodes.- Delta-stepping: good tradeoff — exposes parallelism, efficient for weighted graphs, suitable for distributed implementation; use for batch and parallel online queries.- Landmark/Hub labeling / 2-hop cover: precompute labels (indexing) to answer P2P queries in O(1) or few hops — ideal when query volume is high and graph is fairly static. Cost: expensive preprocessing and storage but huge query speedups; integrates well with ML features.- Approximate methods: ALS-based embeddings or graph neural nets to estimate distances when exactness can be relaxed.

Partitioning strategies:- Edge-cut vs vertex-cut: use vertex-cut for power-law graphs to balance high-degree vertices across machines (used by PowerGraph). Combine with community-aware partitioning (METIS-style) to reduce cross-partition edges for locality.- Replicate hub nodes selectively to reduce communication; maintain consistency via versioned updates.- Store partitions with locality-aware placement (co-locate partitions used by same query patterns).

Handling stragglers & failures:- Checkpoint supersteps (BSP) and incremental snapshotting for long-running batch tasks.- Speculative execution for slow tasks; work-stealing to rebalance load when stragglers identified.- For online queries: make operations idempotent; use timeouts and retry; route around failed partitions using replicas.- Use incremental precomputation (landmarks/labels) with background reconciliation so a failure doesn’t block queries.

ML engineer considerations:- Precompute graph features (embeddings, centralities, landmark labels) offline in BSP cluster, store in feature store for model training/serving.- Expose feature/graph-query microservices for model online inference; batch-refresh labels/embeddings and use warm caches.- Monitor metrics: query latency, partition imbalance, network traffic; use autoscaling and rolling upgrades.

Trade-offs summary:- Exact distributed shortest path (delta-stepping) gives correctness at cost of runtime/comm; landmark/labeling trades preprocessing/storage for very fast queries; choose based on query rate, graph dynamics, and latency SLOs. Use vertex-cut + replication for scale; BSP for batch, async services for low-latency P2P.

HardTechnical

52 practiced

Prove that Dijkstra's algorithm returns correct shortest paths for graphs with non-negative edge weights. Then give a counterexample graph with a negative-weight edge that causes Dijkstra to fail, and explain which property of the algorithm is violated by negative weights.

Sample Answer

Proof sketch (correctness for non‑negative weights)1) Invariant: when Dijkstra extracts a vertex u from the priority queue (marks it "final"), the distance d[u] is the length of a shortest s→u path. 2) Base: s is extracted first with d[s]=0, trivially correct. 3) Inductive step: assume invariant holds for every vertex extracted before an extraction step. Let u be the next extracted vertex with current tentative distance d[u]. For contradiction, suppose there is a shorter s→u path P of length L < d[u]. Let v be the first vertex on P that is not yet extracted; let x be its predecessor on P (x is extracted). Then the subpath s→x is shortest (by minimality of v), so d[x] equals dist(s,x). When x was extracted, algorithm relaxed edge (x,v) and would have set d[v] ≤ d[x] + w(x,v) = length(s→v) (because edge weights ≥ 0). Repeating relaxation along P would imply d[u] ≤ L, contradiction. Thus no shorter path exists and the invariant holds. Since every vertex eventually either gets a final distance or remains unreachable, Dijkstra returns correct shortest paths.

Counterexample with a negative-weight edgeGraph: vertices {s,a,b}; edges: s→a weight 1, s→b weight 4, a→b weight -3. True shortest s→b path is s→a→b with length -2, but Dijkstra fails:- d[s]=0, relax: d[a]=1, d[b]=4. Extract a (d=1), relax a→b: d[b]=1+(-3)=-2. But if extraction order were s, b (4), then a (1) — concretely, if implementation extracted b before a (e.g., ties or other structure), or consider variant where initial d[b]=4 is extracted before the queue is updated — standard Dijkstra assumes once extracted, distances won't decrease. The key violated property is monotonicity/greedy choice: with non‑negative weights, any path extended from the currently smallest tentative distance cannot later be improved via a path through an extracted vertex. Negative edge weights break that guarantee: a vertex considered final can later be improved via a path going through a previously non‑final vertex, so the greedy extraction is not safe.

Which property is violated- The greedy-safe invariant: "finalized distances never decrease" relies on all edge weights ≥ 0. Negative weights allow a finalized vertex's true shortest distance to be lower than the extracted tentative distance, invalidating Dijkstra's correctness. Use Bellman–Ford for graphs with negative weights (it handles negative edges and detects negative cycles).

MediumTechnical

49 practiced

Edge weights in your routing graph change frequently due to traffic. As an ML engineer responsible for route suggestions, propose an architecture for incremental shortest-path updates, caching strategies, and rules for when to recompute routes versus reuse cached results. Discuss latency, consistency, and user experience trade-offs.

Sample Answer

Clarify requirements & constraints:- Soft real-time: user expects route <1s. Edge weights update frequently (seconds–minutes). Must balance freshness vs. compute cost and UX (avoid flapping).

Proposed architecture (high-level):1. Ingestion layer: stream traffic updates into a time-partitioned changelog (Kafka).2. Graph store: base static graph + mutable weight layer in a graph DB / in-memory service (Redis/Tile38) supporting incremental updates.3. Incremental shortest-path service: - Use a hierarchical routing engine (Contraction Hierarchies or multi-level Dijkstra) that supports dynamic edge-weight deltas. - Apply localized updates: recompute affected CH shortcuts or run targeted partial Dijkstra from affected vertices rather than global recompute.4. Cache layer: - Two-tier cache: global route-cache (LRU + TTL) keyed by (origin, destination, departure_time_bucket, routing_profile, max_age_flag) and per-user personalization cache. - Materialized segments cache for common subpaths (tile-based).

Rules for recompute vs reuse:- Immediate reuse: if cached route age <= soft staleness threshold (e.g., 30s) and estimated travel-time drift <= epsilon (based on propagated delta), return cached.- Partial recompute: if drift > epsilon for segments overlapping recent updates, stitch cached route but recompute only affected segments.- Full recompute: if origin/destination in affected region or drift > hard threshold or user requests fastest/real-time route.

Latency, consistency & UX trade-offs:- Latency: caching and partial updates keep p95 < 1s. Full recompute is slower; route service should fall back to cached route with a “traffic-aware” freshness indicator if recompute exceeds latency SLA.- Consistency: eventual consistency acceptable; provide confidence score & ETA uncertainty to user. For critical scenarios (emergency routing), enforce stricter fresh recompute.- UX: avoid route flapping—only surface new route if improvement exceeds UX_delta (e.g., > 2 minutes or 10% faster) and user is en-route. Provide passive updates and allow user to opt-in for aggressive re-routing.

Monitoring & validation:- Telemetry for cache hit rates, recompute frequency, user acceptance of reroutes.- A/B test thresholds (epsilon, TTL) to optimize cost vs satisfaction.

This design balances compute cost with freshness through localized incremental updates, intelligent caching, and clear rules controlling when to recompute versus reuse, while surfacing route uncertainty to preserve user trust.

Unlock Full Question Bank

Get access to hundreds of Shortest Path and Pathfinding Algorithms interview questions and detailed answers.

Join thousands of developers preparing for their dream job.