1

以下に記述したコードに Dijkstras Algorithm を書き込もうとしています。しかし、これを開始する方法がわかりません。オンラインの情報源から少し見直しましたが、実際に機能させる方法はまだわかりません. 私はそれを評価パスメソッドに配置することを好みます。次に、メニュー オプションでこのメソッドを呼び出し、並べ替えアルゴリズムを実行します。

ご参考までに。都市 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

これは、ダイクストラのアルゴリズムの擬似コードです。おそらく役立つでしょう..

これにより、開始都市から各都市までの最短距離が設定されます。

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 クラスを作成してから、ノード グラフを作成してみてください。

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 リストを参照して、グラフのトラバーサルを行います。

また、ダイクストラ アルゴリズムの一部であるため、グラフ トラバーサル中に見つかったパスとコストを追跡するために、もう 1 つのクラスが必要です。私が大学で書いた迷路を実行するプログラムの場合、最短経路を見つけた後でもそのようなデータを保持することが非常に役立つことがわかりました. これを使用して、迷路内の現在のポイントからの最速パスを表示しました。アルゴリズムが一度実行された後は、追加の計算は必要ありません。公平を期すために、アルゴリズムをゴールから迷路内のすべてのポイントまで逆方向に実行して、最も遠いポイントを決定し、そこからプレーヤーを開始できるようにしました ><

于 2011-06-29T02:25:36.960 に答える