如何設計給定地圖的路線圖

Question

這是班加羅爾地鐵地圖。

現在我設計一個應用程序，應該告訴用戶一個源和目的地之間的停靠次數。現在假設用戶只需從藍線的一個站點到藍線的其他站點。由於此圖像中..

現在我們可以看到，應該說塔爾登機點爲1，和目標將是2並且有6個站之間。如何計算中間的停車次數以及距離。如果線路發生變化，用戶希望從BlueLine前往YellowLine，該怎麼辦？

我有一個字符串數組每一行的形式站的名稱。這裏是數組..

String[] greenline = {"Bangalore International Exhibition Center", "Jindal", "Manjunathnagar", "Nagasandra", "Dasarahalli", "Jalahalli", "Peenya Industry", "Peenya", "Yeswanthpur Industry", "Yeswanthpur", "Sandal Soap Factory", "Mahalaxmi", "Rajajinagar", "Kuvempu Road", "Srirampura", "Sampige Road", "Kempegowda Interchange", "Chikpet", "K R Market", "National College", "Lalbagh", "South End Circle", "Jayanagar", "R V Road Interchange", "Banashankari", "J P Nagar", "Puttenahalli", "Anjanapura Cross Road", "Krishna Leela Park", "Vajrahalli", "Thaighattapura", "Anjanapura/NICE Junction"}; 

String[] blueline = {"Kengeri", "R V College of Engineering", "Bangalore University Cross", "Rajarajeshwari Nagar", "Nayandahalli", "Mysore Road", "Deepanjali Nagar", "Attiguppe", "Vijayanagar", "Hosahall1i", "Magadi Road", "City Railway Station", "Kempegowda Interchange", "Sir M Vishweshwariah", "Vidhana Soudha", "Cubbon Park", "M G Road Interchange", "Trinity", "Halasuru", "Indiranagar", "S V Road", "Baiyyappanahalli", "Jyotipura", "K R Puram", "Mahadevpura", "Garudacharpalya", "Doddanekkundi Induatrial State", "Vishweshwariah Industrial State", "Kundanahalli", "Vydhehi Hospital", "Satya Sai Medical Institute", "ITPB", "Kadugodi Industrial Area", "Ujjwal Vidhyalaya", "Whitefield"}; 

String[] redline = {"Nagawara", "Arabic College", "Venkateshpura", "Tannery Town", "Pottery Town", "Cantonment Railway Station", "Shivajinagar", "M G Road Interchange", "Vellara Junction", "Langford Town", "Mico Bosch", "Dairy Circle", "Swagath Road Cross", "Jayadeva Hospital Interchange", "J P Nagar 4th Phase", "IIMB", "Hulimavu", "Gottigere"}; 

String[] yellowline = {"R V Road Interchange", "Ragigudda Temple", "Jayadeva hospital Interchange", "BTM Layout", "Silk Board", "HSR Layout", "Oxford College", "Muneshwara Nagar", "Chikkabegur", "Basapura Road", "Hosa Road", "Electronics City 1", "Electronics City 2", "Huskur Road", "Hebbagodi", "Bommasandra"}; 

有人請幫助。提前Thanx。

Answer 1

首先將行列表轉換爲您要搜索的圖形。

• 讓每個節點保持其名稱，邊緣的列表，並從源（最初無窮大）的距離，並且在最佳路徑

• 讓每個邊緣保持兩個節點的前一個節點，行它屬於以及其成本。

• 準備串節點的哈希映射，稱爲「節點」

• 準備一組節點，稱爲「轉移節點」。你可以使用哈希映射字符串（名稱）=>節點。
• 對於每一行：
  • 如果「節點」沒有條目的第一站的條目，創建一個新節點並將其添加到「節點」。
  • 爲除第一個每個站：
    • 如果「節點」對這個站的條目，創建一個新的節點，並把它添加到「節點」。
    • 創建加入此站和前一站的新邊緣。它的成本是統一的。
    • 將此邊添加到兩個工作站的邊緣列表中
    • 如果現在任一節點屬於多個行（查找成功），則將此工作站添加到「傳輸節點」。

（注：因爲你的行存儲在一組變量，你可以:)

private HashMap<Node> nodes; 
private void addLine (String[] stops, String name){...}; 
// ... (...){ ... 
addLine(greenline, "green line"); 
addLine(blueline, "blue line"); 
//... 

如下如果轉移成本爲零執行 「每行」，添加傳送費用：

• 爲每個節點在 「傳送節點」：
  • 對於使用該節點的每一行：
    • 創建一個以原始節點命名的新節點。
    • 全部重定向（一個或兩個）邊緣該行新的節點 - 改變自己的源或目標，並把它們添加到新節點邊列表。
  • 對於每對新站的節點
    • 創建一個新的邊緣將它們連接，而該邊緣添加到這兩個節點的邊列表。其成本是轉移成本。

現在，找到從源到目的地的最廉價的路徑。我將展示Dijkstra的算法：

• 準備節點的優先級隊列，稱爲「打開設置」。如果轉移成本爲零或一，您可以使用普通的隊列。
• 源節點添加到「開集」。如果起始站是中轉站，則將所有關聯節點添加到「打開設置」。
• 設置源節點的距離從所述源是零
• 重複
  • 「從」，從「開集」彈出一個稱爲節點。如果不存在這樣的元素，則是錯誤的。如果節點對應於目標站，則打破循環，記住「來自」。
  • 對於此節點的每個鄰居，稱爲「to」：
    • 計算「到」的新距離。它是「從」的距離加上連接邊緣
    • 如果新的距離比當前距離短爲「到」的長度：
      • 更新的距離爲「到」。
      • 更新的前緣「到」是「從」和「到」之間的邊緣。
      • 如果距離是無限遠，加上「以」到「開集」
      • 其他更新的位置「到」中的「開集」
• 收集沿着最佳路徑的邊緣：
• 以空的邊緣列表開頭
• 讓當前節點爲「from」。
• 而當前節點具有已定義的前面邊緣：
  • 否則前面的邊緣添加到邊緣的名單
  • 讓當前節點是在這個邊緣

其他節點現在剩下的是讀取路徑：

• 將邊緣計數器初始化爲1
• 對於邊緣列表中的每條邊：
  • 如果這是第一條邊，則輸出「以旅行edge.line從start開始」。
  • 否則，如果前一個邊沿是傳輸邊沿，則輸出「在count停止之後，傳輸到edge.line，在prevEdge.node[0].name」並重置邊沿計數器。
  • 否則遞增邊計數器。
• 輸出「%count停止後，退出%target」。