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的最短路径和距离算法？

回答

相关问题