Нужна помощь в написании алгоритма Дейкстры

Question

Я пытаюсь написать Алгоритм Дейкстры в код, который я написал ниже. Но я не уверен, как начать делать это. Я просмотрел его немного из онлайн-источников, но я до сих пор не уверен, как заставить его работать. Я предпочитаю помещать его в метод методов оценки. Затем используйте параметр меню, чтобы вызвать этот метод, и он выполняет алгоритм сортировки.

FYI. Я сортирую кратчайший путь от города А до города Б на километры и цены.

Ниже приведен код.

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

вот некоторые псевдо код для алгоритма Дейкстры, возможно, это поможет ..

это установит кратчайшее расстояние до каждого города из стартового города ..

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, а затем создайте граф узлов вместо использования списков.

Алгоритм Дейкстры - алгоритм обхода графика, и если вы попробуете это просто использовать массив, вы столкнетесь с некоторыми семантическими проблемами, разделяющими значения, представляющие какие пути. (Глядя на метод ввода пути, он выглядит, как вы уже есть)

Может быть, вы хотите создать некоторые классы, такие как:

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

Это даст вам реальную структуру графа, чтобы пройти, и делает семантический проблема ввода гораздо менее проблематична, так как вы можете искать города из массива, а затем добавлять дорогу на основе заданных входных значений. Затем выполняется обход графика, просматривая список подключений по каждой записи города.

Вы также хотите, чтобы еще один класс отслеживал ваши пути и затраты, найденные во время обхода графика, так как это часть алгоритма Дейкстры. Я нашел такие данные даже после того, как нашел кратчайший путь, чтобы быть очень полезным в случае программы запуска лабиринта, которую я написал в колледже. Мы использовали его для отображения самого быстрого пути от текущей точки в лабиринте, без каких-либо дополнительных вычислений, необходимых после того, как алгоритм работал один раз. Хотя, честно говоря, мы запустили алгоритм назад от цели до всех точек в лабиринте - чтобы определить самый дальний момент - чтобы мы могли начать играть там> <