Scheitelgewicht mit Dijkstras kürzestem Pfadalgorithmus einstellen

Question

Neu in Java.

Was ich versuche zu machen ist eine gerichtete Grafik, die eine Stadt darstellt. Die meisten Vertices sind nur Straßen, aber einige sind touristische Seiten, die Gewichte haben (da man dort für einige Zeit bleiben muss). Ich arbeite mit Dijkstra kürzester Weg Algorithmus und hat einige Ausgabe für das Hinzufügen der Vertices Gewichte in es gemacht.

Allerdings tritt das Problem auf, dass, wenn ich einen Scheitelpunkt als eine Tour-Site setze und ihm ein Gewicht gebe, der Scheitelpunkt kein Gewicht zu haben scheint, wenn es das erste Mal besucht wird. Das Gewicht zeigte sich dann, wenn der Scheitelpunkt das zweite Mal besucht wurde. Ich weiß nicht, wo das Problem war, aber ich würde erraten es ist irgendwo, dass ich nicht direkt die ursprünglichen Variablen bearbeiten.

Die ausgedruckten Zeilen sind unten zwischen * * markiert. Einer ist in CalculateShortest(), ein anderer in 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()); 
      * 
     } 
    } 
} 

Ausgang des Leitungsdruckes, das Problem zeigt (nicht Hauptmethode Ausgang umfasst):

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 

für jede Ecke, getdist() den Abstand von der Quelle Scheitelpunkt selbst zurück, und getCost() geben Sie den Abstand plus das Gewicht des Scheitelpunkts zurück.

Meine Hauptmethode ist unten. Die addNodeEdge() wurde getestet, um gut zu funktionieren. Ich verwende ein Beispiel (siehe Foto unten) von Dijkstra Algorithm in Java und ABCDEF ist 123456 in meinem Fall. Zusätzlich zu der Grafik, bin ich versucht, D (was Scheitelpunkt 4) als eine Website mit einem Gewicht von 30 zu machen. 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 
} 

würde ich den kürzesten Weg zu E (Scheitel 5) 30 und mit F (Vertex 6) 25 erwarten, da der Weg durch D (Scheitelpunkt 4) mit einem Gewicht von 30 zu groß ist. Wie auch immer, was ich hier habe, nachdem ich D's Gewicht geändert habe, ist genau das gleiche, bevor ich D Gewicht hinzugefügt habe. Wie ich oben erklärt habe, denke ich, das Problem ist mit D Gewicht ändern ... Jede Hilfe wäre sehr geschätzt.

Answer 1

Auch wenn Sie die gesetzten und nicht ausgeglichenen HashSets löschen, ist die Variable, die den kürzesten Pfad zu einem Knoten verfolgt, der Abstand der GraphNode-Instanzvariablen. Die Entfernung für den Knoten 5 wird nicht von dem Wert 24 zurückgesetzt, nachdem calculateShortest das erste Mal ausgeführt wurde, und bleibt natürlich nach dem Aufruf der Methode nach dem Einstellen der Standortzeit von Knoten 4 auf 30 gleich.

Eine mögliche Lösung ist ändern Sie den Anfang calculateShortest() alle Knotenabstände zurücksetzen:

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

auch dauerte es einige Zeit, um diese ein, um herauszufinden, vor allem, weil der Code, den Sie geschrieben ist ziemlich schlecht formatiert.Das nächste Mal bitte vermeiden Sie, geschachtelte Klassen zu posten und auch alle potenziell relevanten Implementierungsdetails, die keine trivialen Getter/Setter sind (wie addNodeEdge). Du weißt nie, wo sich dieser lästige Bug verstecken könnte!