Falsche Ausgabe in Dijkstra-Implementierung

Question

Ich versuche, Dijkstra-Algorithmus mit Adjazenzliste und Prioritätswarteschlange zu implementieren, aber für einige der Scheitelpunkte falsche Ausgabe zu erhalten. Da es in der eingebauten Prioritätswarteschlange in Java keine Methode "depreveKey" gibt, füge ich den neuen Vertex hinzu (mit aktualisiertem Abstand von der Quelle). Kann mir jemand sagen, wo ich mich irre? Mein Code ist:

class Graph3 { 
    private int V; 
    private ArrayList<Integer> adj []; 
    Map<String, Integer> weight; //for O(1) lookup of edge weight 
    PriorityQueue<Vertex> minHeap; 
    int d []; 
    int p[]; 
    boolean visited []; 
    Graph3(int n) { 
     this.V = n; 
     adj = new ArrayList[n]; 
     for(int i=0; i<n; i++) { 
      adj[i] = new ArrayList<Integer>(); 
     } 
     weight = new HashMap<String, Integer>(); 
     minHeap = new PriorityQueue<Vertex>(n, new Vertex()); 
     visited = new boolean[n]; 
     Arrays.fill(visited, false); 
     p = new int[n]; 
     Arrays.fill(p, -1); 
     d = new int[n]; 
     Arrays.fill(d,Integer.MAX_VALUE); 
    } 
    public void addEdge(int a, int b, int w) { 
     adj[a].add(b); 
     weight.put(a+","+b,w); //cost of edge(a,b) 
    } 

    public void calculateShortest(int source) { 
     d[source] = 0; 
     visited[source] = true; 
     for(int i=0; i<V; i++) minHeap.offer(new Vertex(i,d[i])); 
     while(!minHeap.isEmpty()) { 
      Vertex u = minHeap.poll(); 
      relaxEdges(u); //relax all outgoing edges of u 
     } 
     for(int i=0; i<d.length; i++) { 
      System.out.println("Shortest path from "+source+" to vertex "+i+" = "+d[i]); 
     } 
    } 

    public void relaxEdges(Vertex u) {  
     for(int i: adj[u.getName()]) { 
      if(!visited[i]) { 
       int alt = d[u.getName()] + weight.get(u.getName()+","+i); 
       if(d[i] > alt) { 
        d[i] = alt; 
        Vertex temp = new Vertex(i,d[i]); 
        minHeap.offer(temp); 
        p[i] = u.getName(); 
        visited[i] = true; 
       } 
      } 
     } 
    } 
} 
//to be used for binding every vertex with dval for use in PQ 
class Vertex implements Comparator<Vertex> { 
    int name; 
    int dval; //current min distance from source 
    public Vertex() { 

    } 
    public Vertex(int name, int dval) { 
     this.name = name; 
     this.dval = dval; 
    } 
    public int getName() { 
     return name; 
    } 
    public void setName(int name) { 
     this.name = name; 
    } 
    public int getDval() { 
     return dval; 
    } 
    public void setDval(int dval) { 
     this.dval = dval; 
    } 
    public int compare(Vertex a, Vertex b) { 
     return (a.dval - b.dval); 
    } 
} 
public class DijkstraShortestPath { 

    public static void main(String args []) { 
     Graph3 g = new Graph3(9); 
     g.addEdge(0, 1, 4); 
     g.addEdge(0, 7, 8); 
     g.addEdge(1, 2, 8); 
     g.addEdge(1, 7, 11); 
     g.addEdge(2, 3, 7); 
     g.addEdge(2, 8, 2); 
     g.addEdge(2, 5, 4); 
     g.addEdge(3, 4, 9); 
     g.addEdge(3, 5, 14); 
     g.addEdge(4, 5, 10); 
     g.addEdge(5, 6, 2); 
     g.addEdge(6, 7, 1); 
     g.addEdge(6, 8, 6); 
     g.addEdge(7, 8, 7); 

     g.calculateShortest(0); 
    } 
} 
**My Output :** 
Shortest path from 0 to vertex 0 = 0 
Shortest path from 0 to vertex 1 = 4 
Shortest path from 0 to vertex 2 = 12 
Shortest path from 0 to vertex 3 = 19 
Shortest path from 0 to vertex 4 = 28 
Shortest path from 0 to vertex 5 = 16 
Shortest path from 0 to vertex 6 = 18 
Shortest path from 0 to vertex 7 = 8 
Shortest path from 0 to vertex 8 = 15 
**Correct Output :** 
Shortest path from 0 to vertex 0 = 0 
Shortest path from 0 to vertex 1 = 4 
Shortest path from 0 to vertex 2 = 12 
Shortest path from 0 to vertex 3 = 19 
Shortest path from 0 to vertex 4 = 21 
Shortest path from 0 to vertex 5 = 11 
Shortest path from 0 to vertex 6 = 9 
Shortest path from 0 to vertex 7 = 8 
Shortest path from 0 to vertex 8 = 14 

Answer 1

Etwas, das aus ist, ist, dass Sie visited[i] = true für alle benachbarten Knoten festgelegt, die in relaxEdges aktualisiert. Der Dijkstra-Algorithmus setzt immer nur den gerade bearbeiteten Knoten, nicht die Nachbarn. Ich nehme an, dass das ist, warum Sie falsche Ausgabe erhalten. Löschen Sie diese Zeile und fügen Sie stattdessen visited[u.getName()] = true in der while-Schleife hinzu.

Da Sie Knoten mehrmals zur Warteschlange hinzufügen, sollten Sie auch direkt in der while-Schleife auf visited[u.getName()] testen, damit die Knoten nicht mehrfach verarbeitet werden.

Dann zuweisen Sie p[i], aber nie verwenden.

Und schließlich, ich rate, eine Edge Klasse zu haben, weil die Darstellung von Kanten als String-verkettete ganze Zahlen sicher klobig ist.