Найти мин в связанном списке
Я пытаюсь найти минимум в связанном списке вершин. Это то, что я написал, но это ошибочно. Я не получаю сообщения об ошибке, но моя программа не работает, и я думаю, что это источник ошибки. Что я делаю неправильно?
Iterator itr = vertices.iterator();
Vertex smallest= getVertex(s);
Vertex temp;
while (itr.hasNext()){
smallest=(Vertex)itr.next();
if (itr.hasNext() && vertices.size()> 1 ){//there are at least 2 vertices left
temp = (Vertex)itr.next();
if (temp.distance< smallest.distance){
smallest = temp;
}
}
}
Он должен давать мне кратчайший путь на графике, и путь, который он дает мне, не самый короткий.
Ответы 1
Проблема в том, что вы потребляете два элемента из итератора на каждой итерации (через itr.next()), поэтому это означает, что вы сравниваете только некоторые элементы:
1----2----3-----4-----5-----6
\----/ \-----/ \-----/
Вы сравниваете 1 и 2; 3 и 4; 5 и 6; но не 2 и 3; 4 и 5.
Самый простой способ решить эту проблему - сохранить предыдущую вершину:
Vertex prev = itr.next();
while (itr.hasNext()) {
Vertex current = itr.next();
// Compare prev and current
prev = current;
}
Также обратите внимание, что вы можете избежать приведений (Vertex), если объявите итератор с параметром типа:
Iterator<Vertex> itr = vertices.iterator();
Еще лучше было бы использовать расширенную петлю for: for (Vertex current : vertices)
@Andreas, за исключением того, что вы не хотите обрабатывать первый элемент отдельно в цикле.
Вот почему вы должны инициализировать min нулевым значением перед циклом, что, кстати, также исправляет ошибку, из-за которой код выдает NoSuchElementException, если vertices пуст. Затем вы меняете оператор if на if (min == null || current.distance < min.distance) { min = current; } и решаете, какой код должен делать, если min равен нулю после цикла, например return Optional.ofNullable(min)
Ваш ответ prev = current и комментарий кода Compare prev and current кажутся неправильными, поскольку цель - «найти минимум в связанном списке вершин», также известная как переменная smallest в коде вопроса. Это не цель сравнения соседних значений.
@ Андрей, а, наверное, я видел вопрос, который хотел увидеть.
"но моя программа не работает" вы имеете в виду, что она дает вам неправильный ответ?