ETA / Shortest Path Calculation on Map

Question

Given a map represented as a graph of nodes (semantic map nodes) with weighted edges representing distances or travel times between nodes, calculate the shortest path (and/or estimated time of arrival, ETA) between a given start node and one or more target nodes. The problem is intentionally left somewhat vague — candidates are expected to clarify requirements (e.g., directed vs. undirected graph, edge weight semantics, single vs. multiple targets) before implementing. Similar to LeetCode 743 (Network Delay Time).

AceOffer · Accepted Answer

Given a map represented as a graph of nodes (semantic map nodes) with weighted edges representing distances or travel times between nodes, calculate the shortest path (and/or estimated time of arrival, ETA) between a given start node and one or more target nodes. The problem is intentionally left somewhat vague — candidates are expected to clarify requirements (e.g., directed vs. undirected graph, edge weight semantics, single vs. multiple targets) before implementing. Similar to LeetCode 743 (Network Delay Time).

Reported follow-ups:
1. What clarifying questions would you ask before coding? (e.g., directed or undirected? negative weights possible? single or multiple targets?) (when: After candidate states the problem)
2. What is the time and space complexity of your solution? (when: After Dijkstra solution is presented)
3. How would you modify your approach if there are multiple target nodes and you need the shortest path to all of them? (when: Multiple target nodes variant)

**Alternative approaches:** Bellman-Ford (Handles negative edge weights but runs in O(VE), much slower than Dijkstra for typical non-negative map edge weights.); A* Search (Uses a heuristic (e.g., Euclidean distance) to guide search toward a single target faster than Dijkstra, but more complex to implement and heuristic must be admissible.); BFS (unweighted graph) (Optimal and simpler if all edges have equal weight, but inapplicable when edges have varying distances/times.)

ETA / Shortest Path Calculation on Map

Problem Overview

Follow-up Arc

Approach Trade-offs

Practice

Approach	Notes
Bellman-Ford	Handles negative edge weights but runs in O(VE), much slower than Dijkstra for typical non-negative map edge weights.
A* Search	Uses a heuristic (e.g., Euclidean distance) to guide search toward a single target faster than Dijkstra, but more complex to implement and heuristic must be admissible.
BFS (unweighted graph)	Optimal and simpler if all edges have equal weight, but inapplicable when edges have varying distances/times.