Java的最短路徑和距離算法？

在下面的代碼我試圖計算兩個城市之間的距離。用戶將進入一個城市名和一個城市，那麼用戶將進入距離這些城市之間，終於進入這些城市之間旅行的價格。我沒有得到它評估，因爲我不確定我將如何做到這一點。我的問題是我正在尋找關於如何做這件事的指針和建議。Java的最短路徑和距離算法？

import java.io.*; 
import java.util.*; 

public class CityCalcultor { 

    static LinkedList<String> cities = new LinkedList<String>(); 
    static LinkedList<Integer> distance = new LinkedList<Integer>(); 
    static LinkedList<Integer> price = new LinkedList<Integer>(); 

    public static void main(String[] args) throws IOException { 
     Scanner input = new Scanner(System.in); 
     String text; 
     int option = 0; 
     while (true) { 
      System.out.println("\nWhat would you like to do:\n" 
       + "1. Add a city to the system\n" 
       + "2. Add a path to the system\n" 
       + "3. Evalute paths\n" 
       + "4. Exit\n" + "Your option: "); 
      text = input.nextLine(); 
      option = Integer.parseInt(text); 

      switch (option) { 
       case 1: 
        EnterCity(); 
        break; 
       case 2: 
        EnterPath(); 
        break; 
       case 3: 
        EvalutePaths(); 
        break; 
       case 4: 
        return; 
       default: 
        System.out.println("ERROR INVALID INPUT"); 
      } 
     } 
    } 

    public static void EnterCity() { 
     String c = ""; 
     LinkedList<String> cities = new LinkedList<String>(Arrays.asList(c)); 
     Scanner City = new Scanner(System.in); 
     System.out.println("Please enter the city name "); 
     c = City.nextLine(); 
     cities.add(c); 
     System.out.println("City " + c + " has been added "); 
    } 

    public static void EnterPath() { 
     Scanner Path = new Scanner(System.in); 
     int d = 0; 
     int p = 0; 
     System.out.println("Enter the starting city "); 
     System.out.println(); 
     System.out.println(Path.nextLine()); 
     System.out.println("Enter the ending city "); 
     System.out.println(Path.nextLine()); 
     System.out.println("Enter the distance between the two cities "); 
     d = Path.nextInt(); 
     for (d = 0; d > 0; d++) { 
      distance.add(d); 
     } 
     System.out.println("Enter the price between the two cities "); 
     p = Path.nextInt(); 
     for (p = 0; p > 0; p++) { 
      price.add(p); 
     } 
     System.out.println("The route was sucessfully added "); 
    } 

    private static void EvalutePaths() { 
    } 
}

來源

2011-06-28 allencoded

這就引出了一個問題：您是否在尋找一個解決旅行推銷員（如@trashgod建議）？這個問題全部是關於尋找一次訪問每個城市的最短旅程。或者，你是否正在尋找任何兩個城市之間的最短路線（一個更容易的問題）？請驗證您的術語*評估*的含義。 –

又見[旅行推銷員問題]（http://en.wikipedia.org/wiki/Travelling_salesman_problem）。 – trashgod

那麼...這只是查找任何兩個城市之間的最短路線。 – allencoded

有兩種方法，我可以理解你的問題：你要麼要評估（對城市之間的每一個可能的路徑這在技術上是無限的，除非你限制重訪城市），或者你想找到從城市到城市的最短距離/最便宜的方式。

我不喜歡試圖找出第一個，我敢肯定你指的是第二，所以我與去。

的解決問題的方法是你的城市，並用圖，其中每個頂點是城市之間的航線模式，每邊是兩個城市之間的直接路徑。邊緣通過城市之間的距離或通過旅行成本加權。

然後，您可以應用Dijkstra's Algorithm（或其中一個變體）來查找總體權重最小（即最小距離或最低成本）的任何源頂點（出發城市）與所有其他頂點（目標城市）之間的路徑，。如果您依次將每個頂點應用此算法作爲源，那麼您將在任何兩個城市之間建立一個最便宜的路線的完整模型。

來源

2011-06-28 02:27:08

是的，第二個！ Dijkstra的算法是最好的。有關如何將其實施到我所擁有的任何想法？ – allencoded

計算最短路徑的非常標準的方式是A*

來源

2011-06-28 02:21:09

我不知道爲什麼這是被低估的，因爲[Dijkstra的算法]（http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm）[可以被看作A *的特例]（http： //en.wikipedia.org/wiki/A%2a_search_algorithm#Special_cases）。 – trashgod

Java的最短路徑和距離算法？

回答

相關問題