1

我正在尝试将 Dijkstras 算法写入我在下面编写的代码中。但我不确定如何开始这样做。我确实从在线资源中对其进行了一些审查，但我仍然不确定如何让它真正发挥作用。我更喜欢将其放入评估路径方法中。然后让菜单选项调用此方法并执行排序算法。

供参考。我正在按里程和价格对从城市 A 到城市 B 的最短路径进行排序。

下面是我的代码。

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();
   distance.add(d);
   System.out.println("Enter the price between the two cities ");
   p = Path.nextInt();

   price.add(p);
   System.out.println("The route was sucessfully added ");


}
private static void EvalutePaths(){


}
}

输出应如下所示::

从西雅图到旧金山的最短路线是 1290 英里。

4

2 回答 2

2

这是Dijkstra 算法的一些伪代码，也许它会有所帮助..

这将设置从起始城市到每个城市的最短距离..

for each city
{
    settled = false
    distance = infinity
}

startingCity.distance = 0

currentCity = startingCity

while not all cities are settled
{
    for each city adjacent to the current city
    {
        newDist = distance from adjacentCity to currentCity

        if newDist < adjacentCity.distance
        {
            adjacentCity.distance = newDist
        }  
    }

    currentCity.settled = true

    currentCity = city closest to currentCity
}
于 2011-06-29T00:58:41.270 回答
1

如果我可以提出一个可能使编码变得更容易的适度建议：尝试创建一个 City 和 Link 类，然后创建一个节点图，而不仅仅是使用 Lists。

Dijkstra 算法是一种图遍历算法，如果您仅使用数组尝试此操作，您将遇到一些语义问题，以区分哪些值代表哪些路径。（看路径输入法，好像你已经是了）

也许您想创建一些类，例如：

public class City {
  String name;
  List<Road> connectingRoads;

}

public class Road {
  List<City> connectingCities;
  Float distance;
  Float price;

  // Technically this COULD be for more than two cities... mainly I wrote it this way simply to make coding and use easier.
  Road(Float distance, Float price, City... connectingCities) {
    this.distance = distance;
    this.price = price;
    connectingCities = new ArrayList(connectingCities);
    for (City city : connectingCities) {
       city.connectingRoads.add(this);
    }
  }
}

这将为您提供要遍历的实际图形结构，并使语义输入问题的问题大大减少，因为您可以从数组中查找城市，然后根据给定的输入值添加道路。然后通过查看每个 City 记录上的 connectedRoads 列表来完成图遍历。

您还需要一个类来跟踪在图遍历期间发现的路径和成本，因为这是 Dijkstra 算法的一部分。我发现即使在找到最短路径之后保留这些数据对于我在大学编写的迷宫运行程序非常有帮助。我们用它来显示迷宫中当前点的最快路径，在算法运行一次后不需要任何额外的计算。虽然公平地说，我们从目标向后运行算法到迷宫中的所有点 - 以确定最远点 - 所以我们可以在那里启动玩家><

于 2011-06-29T02:25:36.960 回答