Dijkstraの最終的な答えの距離として2147483647を出力

Question

ユーザーにはどのようなパスと距離が求められます。その後、Dijkstraのアルゴリズムを使って最短距離を計算します。問題はある程度の距離であり、パスは間違っています。 2147483647の距離があり、パスはnullです。アルゴはゼロを出発点として完全に機能します。どうすれば修正できますか？
ユーザ入力

Enter first path: 0 
Enter second path: 1 
Enter distance: 1 
Do you want to add path again? y 
Enter first path: 1 
Enter second path: 3 
Enter distance: 2 
Do you want to add path again? y 
Enter first path: 3 
Enter second path: 5 
Enter distance: 4 
Do you want to add path again? y 
Enter first path: 1 
Enter second path: 2 
Enter distance: 3 
Do you want to add path again? y 
Enter first path: 0 
Enter second path: 2 
Enter distance: 8 
Do you want to add path again? y 
Enter first path: 0 
Enter second path: 4 
Enter distance: 9 
Do you want to add path again? n 
V D P 
0 2147483647null //this part should be 1 and the path is 1-0 
1 0null 
2 31 - 2 
3 21 - 3 
4 2147483647null // this part should be 10 and the path is 0-4 
5 63 - 5 

もし===================================== ====================================

import java.util.*; 

public class DijkstraAlgo { 
    final static int VERTICES = 6; 

    public static int minDistance(int distance[], Boolean shortestPath[]){ 
     int minDist = Integer.MAX_VALUE; 
     int minIndex = -1; 

     for(int i = 0;i < VERTICES;i++){ 
      if(shortestPath[i] == false && distance[i] <= minDist){ 
       minDist = distance[i]; 
       minIndex = i; 
      } 
     } 

     return minIndex; 
    } 

    public static void dijkstra(int path[][], int startingPoint){ 
     int shortestDist[] = new int[VERTICES]; 
     Boolean shortestPath[] = new Boolean[VERTICES]; 
     String paths[] = new String[VERTICES]; 

     for(int i = 0;i < VERTICES;i++){ 
      shortestDist[i] = Integer.MAX_VALUE; 
      shortestPath[i] = false; 
     } 

     shortestDist[startingPoint] = 0; 

     for(int ctr = 0;ctr < VERTICES - 1;ctr++){ 
      int index = minDistance(shortestDist, shortestPath); 

      shortestPath[index] = true; 

      for(int j = 0;j < VERTICES;j++){ 
       if(!shortestPath[j] && path[index][j] != 0 && shortestDist[index] != Integer.MAX_VALUE && shortestDist[index] + path[index][j] < shortestDist[j]){ 
        shortestDist[j] = shortestDist[index] + path[index][j]; 
        paths[j] = Integer.toString(index) + " - " + " " + Integer.toString(j); 
        System.out.println(shortestDist[j]); 
       } 
      } 
     } 
     printAnswer(shortestDist, VERTICES, paths); 
    } 

    public static void printAnswer(int distance[], int vertices, String paths[]){ 
     System.out.println("V D P"); 
     for(int i = 0; i < VERTICES; i++) 
      System.out.println(i + " " + distance[i] + paths[i]); 
    } 

    public static void main(String args[]){ 
     int start; 
     int end; 
     int path[][] = new int[6][6]; 
     int distance; 

     Scanner input = new Scanner(System.in); 
     String choose; 
     boolean ans = true; 

     while(ans == true){ 
      System.out.print("Enter first path: "); 
      start = input.nextInt(); 
      System.out.print("Enter second path: "); 
      end = input.nextInt(); 
      System.out.print("Enter distance: "); 
      distance = input.nextInt(); 

      path[start][end] = distance; 

      System.out.print("Do you want to add path again? "); 
      choose = input.next(); 
      if(choose.equals("y") || choose.equals("Y")) 
       ans = true; 
      else if(choose.equals("n") || choose.equals("N")) 
       ans = false; 
      else 
       System.out.println("Invalid input!"); 
     } 

     dijkstra(path, 1); 
    } 

} 

Answer 1

私が間違っているのか分かりませんあなたのコードで、正直である。私はそれを通過してデバッグしようとは考えていません。 Eclipseはこれを行うことができます（私がコメントにリンクしているように）。

私が提供するものは、これに近づくためのより良い手段です。データを整数の配列に格納することは複雑なアプローチであり、混乱の原因となります（ここでは明らかです）。 Javaのようなオブジェクト指向言語を使用する主な利点の1つは、コンテキストに関連した一貫した方法でデータを形成できることです。

は、2つのクラスを作成することを検討：

public void createTwoWayLink(DijkstraNode first, DijkstraNode second, int distance) { 
    first.addLink(new DijkstraLink(second, distance)); 
    second.addLink(new DijkstraLink(first, distance)); 
} 

次に評価ダイクストラになるくらいsimplierタスク：

public void computeDijkstras(DijkstraNode startNode, List<DijkstraNode> nodes) { 
    Map<DijkstraNode, Integer> distances = new HashMap<DijkstraNode, Integer>(); 
    for (DijkstraNode node : nodes) { 
     if (node != startNode) { 
      distances.put(node, Integer.MAX_VALUE); 
     } 
     else { 
      distances.put(node, 0); 
     } 
    } 

    List<DijkstraNode> computedNodes = new ArrayList<DijkstraNode>(); 

    DijkstraNode toEval = computeSmallestUncomputedNode(distances, computedNodes); // TODO 

    while (toEval != null) { 
     for (DijkstraLink link : toEval.getLinks()) { 
      if (computedNodes.contains(link.getLinkedNode()) { 
       continue; 
      } 
      int evalDist = link.getDistance() + distances.get(toEval); 
      if (evalDist < distances.get(link.getLinkedNode())) { 
       distances.put(link.getLinkedNode(), evalDist); 
      } 
     } 

     computedNodes.add(toEval); 

     toEval = computeSmallestUncomputedNode(distances, computedNodes); 
    } 

    // distances computed; do whatever. 
} 

あなたは、ノード間の双方向リンクを作成するたびに

public class DijkstraNode { 
    private int label; 
    private List<DijkstraLink> links; 

    public DijkstraNode(int label) { 
     this.label = label; 
     links = new ArrayList<DijkstraLink>(); 
    } 

    public int getLabel() { 
     return label; 
    } 

    public void addLink(DijkstraLink link) { 
     links.add(link); 
    } 

    public List<DijkstraLink> getLinks() { 
     return links; 
    } 
} 

... 

public class DijkstraLink { 
    private DijkstraNode node; 
    private int distance; 

    public DijkstraLink(DijkstraNode node, int distance) { 
     this.node = node; 
     this.distance = distance; 
    } 

    public DijkstraNode getLinkedNode() { 
     return node; 
    } 

    public int getDistance() { 
     return distance; 
    } 
} 

これは完全な実装ではありません。私はあなたの宿題をしたくなかった。しかし、私は、オブジェクト指向設計と内部Javaデータ構造（例えば、使用される Listと Mapオブジェクトなど）を活用することで、実行をより一貫して実行しやすくする方法の例を十分に取り入れることを望みました。お役に立てれば。