Suggest practical approach for answering shortest path queries between addresses

Question

Suggest practical approach for answering shortest path queries between addresses in the USA. Each such query specify a source address and a destination address. Your goal is to preprocess the road map into a reasonable size data-structure that would enable answering such queries efficiently. To clarify possible doubt, assuming the number of houses is about 125M, so a data structure of size proportional to all roughly (125M)^2 is not considered reasonable. The query time should be reasonable, though might not be O(1). As an example, think about data structures (plus and algorithm) that you could download into your smartphone, so it could compute a shortest or almost-shortest path between every two addresses, while the smartphone is offline. (think about approaches that are almost-optimal).

Explanation / Answer

by using Dijkstras shortest path algorithm

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.