圆圈中的Dijkstra算法

Question

我要在Java中开发一个Dijkstra Alogirthm，我有一个问题要问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();

}

Answer 1

PS: the if (next.equals(startNode) was only an idea to stop the loop.

没有必要这样做，当你的 while 条件找不到更多未访问的相邻节点时，它无论如何都会终止。你只需要检查当前访问的节点状态是否为黑色，如果是，则不要将其添加到队列中（之前已经访问过）。

P.S.: 我认为你不需要灰色状态，只需要黑色或白色。立即处理节点，无需拖延

圆圈中的Dijkstra算法

Dijkstra Algorithm in a circle

java

algorithm

dijkstra