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

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

1 голос
/ 29 июня 2011

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

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

Ниже приведен код, который у меня есть. 

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 миль.

Ответы [ 2 ]

2 голосов
/ 29 июня 2011

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

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

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
}
1 голос
/ 29 июня 2011

Если я могу сделать скромное предложение, которое может упростить кодирование: попробуйте создать класс 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);
    }
  }
}

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

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

...