Warum funktioniert der Dijkstra-Algorithmus nicht so, wie er für ein bestimmtes Diagramm sein sollte?

Question

Ich habe den folgenden Code, Dijkstra-Algorithmus, den ich mit Wikipedia's article on the algorithm gemacht habe.

Für den gegebenen Graph (siehe Bild) und den Startknoten (1) gibt es 5 als Abstand zum Knoten (4) zurück, was offensichtlich falsch ist. Geht man jedoch von Knoten (4) aus, gibt es 4 als Abstand zu (1) zurück, was korrekt ist. Was ist falsch in meinem Code?

//source = starting point, adj[] = adjacency list 
private static int dijkstra (int source, ArrayList<Road>[] adj) { 
    HashSet<Integer> vertices = new HashSet<>(); 

    int[] dist = new int[adj.length]; 
    int[] prev = new int[adj.length]; 

    for (int i = 0; i < adj.length; i++) { 
     dist[i] = Integer.MAX_VALUE; 
     prev[i] = Integer.MAX_VALUE; 
     vertices.add(i); 
    } 

    dist[source] = 0; 

    while (!vertices.isEmpty()) { 
     int current = Integer.MAX_VALUE; 
     for (int v: vertices) { 
      if (dist[v] < current) { 
       current = v; 
      } 
     } 
     vertices.remove(current); 

     for (Road v: adj[current]) { 
      int alt = dist[current] + v.distance; 

      if (alt < dist[v.end]) { 
       dist[v.end] = alt; 
       prev[v.end] = current; 
      } 
     } 
    } 
} 

class Road { 
    int end; 
    int distance; 
} 

//This loop builds adjacency list from input such as "1 3 2", where 1 represents 
// starting node, 3 represents end node and 2 represents weight of that edge. 
//start and end values are decremented in order to be 0-indexed 

for (int i = 0; i < M; i++) { 
    int start = in.nextInt() - 1; 
    int end = in.nextInt() - 1 ; 
    int dist = in.nextInt(); 

    adj[start].add(new Road(end, dist)); 
    adj[end].add(new Road(start, dist)); 
} 

Answer 1

Dieses Stück Code verursacht den Fehler:

int current = Integer.MAX_VALUE; 
for (int v: vertices) { 
    if (dist[v] < current) { 
     current = v; 
    } 
} 

ich es sollte annehmen, die nicht besucht Knoten suchen, die den kürzesten Weg vom Start-Knoten hat. Aber dies sollte aussehen eher wie folgt aus:

int currentPathLen = Integer.MAX_VALUE, current = -1; 
for (int v: vertices) { 
    if (dist[v] < currentPathLen) { 
     current = v; 
     currentPathLen = dist[current]; 
    } 
}