Saída incorreta na implementação de Dijkstra - algoritmo

Estou tentando implementar o algoritmo de Dijkstrausando a lista de adjacências e a fila de prioridade, mas obtendo saída incorreta para alguns dos vértices. Como não há um método de fallKey na fila de prioridade embutida em Java, estou adicionando o novo vértice (com a distância atualizada da fonte). Alguém pode aconselhar onde estou enganado? Meu código é:

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

Respostas:

Algo que está desligado é que você define visited[i] = true para todos os nós vizinhos que são atualizados em relaxEdges. O algoritmo de Dijkstra sempre define apenas o nó atualmente processado para ser visitado, não os vizinhos. Eu diria que é por isso que você obtém uma saída incorreta. Exclua esta linha e adicione visited[u.getName()] = true no loop while.

Como você adiciona nós várias vezes à fila, você também deve testar diretamente visited[u.getName()] no laço while, assim os nós não são processados ​​várias vezes.

Então, você atribui a p[i], mas nunca use isso.

E por último, eu aconselho a ter um Edge classe porque representando arestas como inteiros de concatenação de string com certeza é desajeitado.