檢索和存儲路線地圖數據

Question

我正在研究項目，其中要求檢索特定來源和目的地的地圖相關數據。在未來的每一個請求中，這個已經獲取的被緩存的信息將被使用。但是，現在如果源或目的地發生變化，地圖將被重建，其中包括舊的源和目的地。

我的一些問題是：

1. 要使用的數據結構，使搜索很容易和尋找源和目的地之間的所有中間節點是簡單而有效。

2. 我有一個有限的內存資源，從而有在存儲一個非常大的DSC的奢侈品是不可能的。

我正在考慮存儲源和目的地之間的路徑數據列表然而，這可能使搜索作爲我希望避免不惜任何代價進行線性搜索。如果在構建用於存儲路線信息的結構方面存在一些開銷，那麼確定是可以的，但是搜索必須快速且容易。我使用java作爲編程語言。

預先感謝您的任何幫助

Answer 1

你應該代表你的地圖爲圖形。每個位置都會列出所有可以到達的緊鄰地點。通過這種方式，當給定源和目標時，您可以執行DFS或BFS來確定從源到目標的所有路徑和所有中間節點。

既然你有一個給定的源和目的地緩存之間的路由，下一次你構建的數據不同的源或目的，你可以嘗試使用緩存的數據。