需要帮助编写 Dijkstra 算法

Question

我正在尝试将 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 英里。

Answer 1

这是 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
}

Answer 2

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

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);
    }
  }
}

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

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