Dijkstraの最短経路アルゴリズムを使用して頂点の重みを設定する

Question

Javaの初めて。

私がしようとしているのは、有向グラフという都市です。頂点のほとんどは通りだけですが、は、重みがの観光地です（ある程度はそこにとどまっているので）。私はDijkstraの最短経路アルゴリズムと一緒に作業しており、頂点の重みを追加するためのいくつかのエディションを作っています。

しかし、ツアーサイトとして頂点を設定してウェイトを与えると、頂点は最初に訪問されたときにウェイトを全く持たないように見えます。次に、頂点が2回目に訪れたときに体重が表示されました。私はどこに問題があったのかわからないが、私はと思います私はどこかで元の変数を直接編集していません。

プリントアウト行は、* *の下にマークされています。 1つはcalculateShortest（）にあり、もう1つはcalculateMin（）です。

public class Graph 
{ 
    protected HashMap<Integer, GraphNode> ntable = new HashMap<Integer, GraphNode>(); 
    //a hashmap of every node's edge treemap, in which edges are sorted according to weight of each 
    protected HashMap<Integer, TreeMap<Integer, GraphEdge>> etable = new HashMap<Integer, TreeMap<Integer,GraphEdge>>(); 
} 

public class GraphNode 
{ 
    private int val; 
    private boolean site; 
    private boolean hotel; 
    private int time; 
    private int distance = Integer.MAX_VALUE; 
    private LinkedList<GraphNode> shortest = new LinkedList<GraphNode>(); 
} 

public class GraphEdge implements Comparable<GraphEdge> 
{ 
    private int nd1; 
    private int nd2; 
    private int weight; 
} 

public class Path 
{ 
    protected LinkedList<GraphNode> path = new LinkedList<GraphNode>(); 
    Graph g = new Graph(); 
    GraphNode start = new GraphNode(0); 
    protected HashSet<GraphNode> settled = new HashSet<GraphNode>(); 
    protected HashSet<GraphNode> unsettled = new HashSet<GraphNode>(); 

    public Graph calculateShortest(int start) 
    { 
     g.ntable.get(start).setDist(0); 
     unsettled.add(g.ntable.get(start)); 
     while (unsettled.size() != 0) 
     { 
      GraphNode current = getLowestCostNode(unsettled); 
      unsettled.remove(current); 
      TreeMap<Integer, GraphEdge> adjacentE = g.etable.get(current.getVal()); 
      * 
      //printing out below shows vertex has no weight 
      System.out.println("Curr: "+ current.getVal() + " " + current.getSiteTime()); 
      * 
      for (GraphEdge edge: adjacentE.values()) 
      { 
       GraphNode adjacent = g.ntable.get(edge.getEnd()); 
       int cost = edge.getWeight() + current.getSiteTime(); 
       if (!settled.contains(adjacent)) 
       { 
        calculateMin(adjacent, cost, current); 
        unsettled.add(adjacent); 
       } 
      } 
      settled.add(current); 
     } 
    return g; 
} 

    public GraphNode getLowestCostNode(HashSet<GraphNode> unsettled) 
    { 
     GraphNode lowestDistNd = null; 
     int lowestDist = Integer.MAX_VALUE; 
     for (GraphNode nd : unsettled) 
     { 
      int nodeDist = nd.getDist(); 
      if (nodeDist < lowestDist) 
      { 
       lowestDist = nodeDist; 
       lowestDistNd = nd; 
      } 
     } 
     return lowestDistNd; 
    } 

    public void calculateMin(GraphNode evaNd, int cost, GraphNode startNd) 
    { 
     int startDist = startNd.getDist(); 
     if (startDist + cost < evaNd.getDist()) 
     { 
      evaNd.setDist(startDist + cost); 
      LinkedList<GraphNode> shortest = new LinkedList<GraphNode>(startNd.getShortest()); 
      shortest.add(startNd); 
      evaNd.setShortest(shortest); 
      * 
      //print out if the node's distance is changed 
      System.out.println("Change " + evaNd.getVal() + " " + evaNd.getDist()); 
      * 
     } 
    } 
} 

（mainメソッドの出力が含まれていない）問題を示すライン印刷の出力：すべての頂点の

Curr: 1 0 
Change: 2 10 
Change: 3 15 
Curr: 2 0 
Change: 4 22 
Change: 6 25 
Curr: 3 0 
Change: 5 25 
Curr: 4 0 //1st time visiting shows no weight 
Change: 6 23 
Change: 5 24 
Curr: 6 0 
Curr: 5 0 
Curr: 1 0 
Curr: 2 0 
Curr: 3 0 
Curr: 4 30 //2nd time visiting shows weight 
Curr: 6 0 
Curr: 5 0 

、getDist（）は、ソース頂点からそれ自身までの距離を戻す、 getCost（）距離との頂点の距離を返します。

私の主な方法は以下の通りです。 addNodeEdge（）はうまく動作することがテストされています。私はの例を使用しています（下の写真を参照）Dijkstra Algorithm in Javaと私の場合はABCDEFは123456です。グラフに加えて、私はであるD（頂点4）を重みが30のサイトにしようとしています。 Visualization of the graph

public static void main (String [] args){ 
    Path p = new Path(); 
    p.g.addNodeEdge(1, 2, 10); 
    p.g.addNodeEdge(1, 3, 15); 
    p.g.addNodeEdge(2, 4, 12); 
    p.g.addNodeEdge(2, 6, 15); 
    p.g.addNodeEdge(3, 5, 10); 
    p.g.addNodeEdge(4, 6, 1); 
    p.g.addNodeEdge(4, 5, 2); 
    p.g.addNodeEdge(6, 5, 5); 
    p.calculateShortest(1); 
    System.out.println(p.g.ntable.get(5).getDist());//print out 24 

    p.settled.clear(); 
    p.unsettled.clear(); 
    p.g.ntable.get(4).setSite(30); 
    p.calculateShortest(1); 
    System.out.println(p.g.ntable.get(5).getDist());//still print out 24 
} 

30の重量とD（頂点4）を通る経路が大きすぎるので、私はEへの最短パス（頂点5）30を期待し、F（頂点6）25になります。しかし、Dの体重を変更した後に私がここに持っているものは、Dに体重を加える前と全く同じです。私が上で説明したように、問題はDの体重が変化していると思います。どんな助けでも大歓迎です。

Answer 1

解決済みのHashSetと未解決のHashSetをクリアしていても、これまでノードに見つかった最短パスを追跡する変数は、GraphNodeインスタンス変数の距離です。最初にcalculateShortestを実行した後、ノード5の距離は24の値からリセットされず、ノード4のサイト時間を30に設定した後もメソッドを呼び出した後も同じままです。

1つの解決策が考えられますノード間距離の全てをリセットするために）（calculateShortestの始まりを変更：

public Graph calculateShortest(int start) { 
    for (GraphNode n : g.ntable.values()) { 
     n.setDist(Integer.MAX_VALUE); 
    } 
    g.ntable.get(start).setDist(0); 
    ... 

また、それはあなたが投稿したコードはかなり悪いフォーマットされている主な理由は、このいずれかを把握するためにいくつかの時間がかかりました。次回は、ネストされたクラスの投稿を避けてください。また、（getNodeEdgeなどの）簡単なgetter/setterではない可能性のある実装の詳細をすべて含めるようにしてください。その厄介なバグがどこに隠れているのかわからない！