Java的最短路径和距离算法？

Question

在下面的代码中，我试图计算两个城市之间的距离。用户将输入城市名称和城市，然后用户将输入这些城市之间的距离，最后输入这些城市之间旅行的价格。我还没有对其进行评估，因为我不确定我将如何做到这一点。我的问题是我正在寻找关于如何做到这一点的指示和建议。

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() {
    }
}

Answer 1

我可以通过两种方式解释你的问题：你要么想评估城市对之间的每条可能的路径（从技术上讲，这是无限的，除非你限制重新访问城市），要么你想找到最短的距离/最便宜的方式城市到城市。

我不想试图弄清楚第一个，而且我很确定你指的是第二个，所以我就这么做。

该问题的解决方案是使用图表对城市及其之间的路线进行建模，其中每个顶点都是一个城市，每条边是两个城市之间的直接路径。边缘根据城市之间的距离或旅行成本进行加权。

然后，您可以应用 Dijkstra 算法（或其变体之一）来查找任意路径之间的路径源顶点（出发城市）到所有其他顶点（目的地城市）的总权重最小（即最小距离或最低成本）。如果您依次使用每个顶点作为源来应用此算法，您将构建任意两个城市之间最便宜路线的完整模型。

Answer 2

计算最短路径的几乎标准方法是 A*