Dijkstraのアルゴリズムを書くのに助けが必要

Question

私は以下に書いたコードにDijkstrasアルゴリズムを書こうとしています。しかし、私はこれをやり始める方法がわかりません。私はそれをオンラインソースから少し見直しましたが、私はそれを実際に動作させる方法はまだ分かりません。私はそれを評価経路法に入れることを好む。メニューオプションでこのメソッドを呼び出すと、ソートアルゴリズムが実行されます。

FYI。私は、都市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

は

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's Algorithmはグラフトラバーサルアルゴリズムであり、配列を使ってこれを試してみると、どの値がどのパスを表しているかを分ける意味的な問題が発生します。

はおそらく、あなたのようないくつかのクラスを作成します（パスの入力方法を見てみると、それはあなたがすでにあるように見える）：これはあなたに通過する実際のグラフ構造を与える

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のアルゴリズムの一部であるため、グラフトラバーサル中に見つかったパスとコストをもう1つのクラスで管理しておきましょう。私は大学で書いた迷路実行プログラムの場合に非常に役立つように、最短経路を見つけた後でもこのようなデータを保持していることがわかりました。アルゴリズムを一度実行した後に追加の計算をすることなく、迷路の現在のポイントからの最速パスを表示するために使用しました。ゴールから迷路内のすべてのポイントまでアルゴリズムを逆方向に走らせて、最も遠いポイントを決定してください。> <