Мне нужно разработать Dijkstra Alogirthm на Java, и у меня есть вопрос к Dijkstra по кругу.
Так что для дерева или нормального графа без цикла это работает.
Итак, у меня есть статус Белый означает, что не найден, серый = найден, но не обработан, и черный означает, что выполнено.
Поэтому, когда у меня есть цикл, я пробовал if (next.status == Node.Black), но потом он не нашел все узлы.
Итак, вопрос в том, как добавить обнаружение петли и найти все узлы?
Спасибо за помощь и советы
С наилучшими пожеланиями witar7
PS: if (next.equals (startNode) была только идеей остановить цикл.
public void populateDijkstraFrom(Node startNode) {
this.resetState();
PriorityQueue<Node> distanceQueue = new PriorityQueue<Node>();
for (int x = 0; x < nodes.size(); x++) { // for each node
nodes.get(x).distance = Double.POSITIVE_INFINITY; // set distance to inf
nodes.get(x).predecessor = null; // delete existing predecessors
}
startNode.distance = 0.0; // set distance from startNode to zero
startNode.status = Node.GRAY; // mark startNode as active
Node current = startNode;
distanceQueue.add(current); // add startNode to prio queue
while (!distanceQueue.isEmpty()) { // while contains elements
current = distanceQueue.poll(); // set current to head of queue
current.status = Node.BLACK; // mark head as settled
for (Node next : current.getAdjacentNodes() ) { // get all adjacent nodes
if (next.equals(startNode)) {
break;
}
next.status = Node.GRAY;
// stopExecutionUntilSignal();// mark status as found
distanceQueue.add(next);
if (distanceQueue.contains(next)) {
if (next.distance > current.distance + current.getWeight(next)) { // if the found distance is smaller then the existing one
next.predecessor = current; // change distance in node
next.distance = current.distance + current.getWeight(next); // set predecessor
}
}
}
}
this.clearMarks();
}