Почему алгоритм Дейкстры не работает так, как нужно для данного графика?

Question

У меня есть следующий код, алгоритм Дейкстры, который я сделал с помощью Wikipedia's article on the algorithm.

Для данного графика (см. Изображение) и стартового узла (1) он возвращает 5 как расстояние до узла (4), что, очевидно, является ложным. Однако, переходя из узла (4), он возвращает 4 как расстояние до (1), что является правильным. Что не так в моем коде?

//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

Этот кусок кода вызывает ошибку:

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

я предполагаю, что он должен искать Непосещенные узел, который имеет кратчайший путь от запуска вершины. Но это должно выглядеть скорее так:

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