尋找在傳輸網絡中從點A到點B的最近路線的算法？

Question

好吧，我試圖編寫一個基本的程序，可以幫助用戶找到最接近的方式從A點到地鐵網絡中的B點。目前，我在Java中編寫了這個代碼，我有三個類，分別是Station類，Route類和Control類。這個想法是，Route對象在數組列表中存儲有限數量的Station對象，它實際上模擬了包含確切數量站的單個地鐵路線。此外，Station對象可以存儲少量的Route對象，就像同時位於多條路線上的Transit地鐵站一樣。我正在開發的部分是讓用戶進入他們的出發站和目的地站，然後該程序將打印出他們需要傳送的站點列表（必須儘可能最低）以便到達他們的站點目的地。在這個時候，我很驚訝於找到一個很好的算法來完成這部分程序，我可以想象如何編寫可以在複雜網絡中執行此任務的代碼。所以，如果有人有任何想法，請指導我。謝謝。

Answer 1

Dijsktra's Algorithm可以很好地運行以計算單源最短路徑。您也可以預先使用多源最短路徑算法（例如Floyd-Warshall Method）爲每對站預先計算所有最短路徑。

這兩種算法在給定正確的數據結構的情況下都很容易實現（我認爲您可能沒有必要使用Route類，爲什麼不讓每個Station對象包含它的直接鄰居列表？嚴格遵循通用圖形數據結構）。您可以創建一個預先計算的查找表（儘管對於很多站來說這將是很大的），每個站在給定期望的目的站的情況下告訴你從該站，你要移動到哪個鄰站。這實質上是爲每個電臺創建routing tables。