Я пытаюсь реализовать алгоритм Дейкстры, чтобы найти кратчайший путь от начальной вершины до каждой другой вершины в неориентированном взвешенном графе, используя этот псевдокод:
Initialize D(v) = 0 and D(u) = ∞ for u != v
Initialize priority queue Q of vertices using D as key.
while Q is not empty do
u = Q.removeMin()
for each vertex z adjacent to u and in Q do
if D(u) + w((u, z)) < D(z) then
D(z) = D(u) + w((u, z))
update z in Q
return D
отсюда: http://www.csl.mtu.edu/cs2321/www/newLectures/30_More_Dijkstra.htm
Это реализация этого:
public void Dijkstra(int start) {
int[] D = new int[E.length];
for (int i = 0; i < E.length; i++) {
D[i] = Integer.MAX_VALUE;
}
D[start] = 0;
PriorityQueue<Integer> Q = new PriorityQueue<>();
Q.add(start);
while (!Q.isEmpty()) {
Integer u = Q.poll();
System.out.println(u + " ");
for (int z = 0; z < E[u].size(); z++) {
Edge e = E[u].get(z);
if ((D[u] + e.w) < D[e.v]) {
D[e.v] = D[u] + e.w;
Q.add(e.v);
}
}
}
System.out.println(D[E.length - 1]);
}
График реализован с использованием списка смежности, и здесь в коде D (u) расстояние u от v, E.length - длина списка смежности, а w - вес ребра.
Для этого примера: 5 вершин, 6 ребер и пары вершин с весом ребра 0 1 20, 0 2 20, 0 4 40, 1 3 50, 2 3 30 и 3 4 70.
Выходные данные, начиная с 1, должны быть: 1 0 2 3 4 и расстояние 140, но моя реализация выдает: 1 3 4 и расстояние 120.
Мой вопрос заключается в том, почему я получаю этот ответ вместо правильного с моей реализацией.
Если другие части класса необходимы, я опубликую их.
Спасибо за чтение и помощь!