Nieprawidłowe dane wyjściowe w implementacji Dijkstry - algorytm

Próbuję wdrożyć algorytm Dijkstryza pomocą listy przyległości i kolejki priorytetów, ale uzyskując nieprawidłowe wyniki dla niektórych wierzchołków. Ponieważ nie ma metody malejącej wartości w wbudowanej kolejce priorytetów w Javie, dodaję nowy wierzchołek (ze zaktualizowaną odległością od źródła). Czy ktoś może doradzić, gdzie się mylę? Mój kod to:

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

Odpowiedzi:

Coś, co jest wyłączone, jest ustawione visited[i] = true dla wszystkich sąsiednich węzłów, które są aktualizowane relaxEdges. Algorytm Dijkstry zawsze ustawia tylko aktualnie przetwarzany węzeł, ale nie sąsiedzi .. Domyślam się, że to dlatego otrzymujesz niepoprawne dane wyjściowe. Usuń tę linię, a zamiast tego dodaj visited[u.getName()] = true w pętli while.

Ponieważ dodajesz węzły wiele razy do kolejki, powinieneś także bezpośrednio testować visited[u.getName()] w pętli while, więc węzły nie są przetwarzane wiele razy.

Następnie przypisujesz do p[i], ale nigdy z niego nie korzystaj.

I na koniec, radzę mieć Edge class, ponieważ reprezentowanie krawędzi jako łączących się w łańcuchy liczb całkowitych z pewnością jest niepoważne.