CODEWITHSUNDEEP
javaalgorithmdijkstra
wit4r7
wit4r7

Reputation: 135

Dijkstra Algorithm in a circle

I have to develop a Dijkstra Alogirthm in Java and I have a question to Dijkstra in a circle.

So for a Tree or a normal graph without a loop it works.

So I have a Status White means not found, gray = found but not dealt with and black means done.

So when I have a loop I tryed a if (next.status == Node.Black) but then he didn't found all nodes.

So the question is, how can I add a loop detection and found all nodes?

Thanks for help and tips

best regards witar7

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

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();

}

Upvotes: 0

Views: 1061

Answers (1)

LeleDumbo
LeleDumbo

Reputation: 9340

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

There's no need to do this, your while condition will terminate anyway when it can't find anymore unvisited adjacent nodes. You just have to check whether current visited node status is BLACK and if yes, don't add it to the queue (it's already been visited before).

P.S.: I don' think you need GRAY status, just BLACK or WHITE. Deal with the node right away, no need to delay.

Upvotes: 1

Related Questions