CODEWITHSUNDEEP
javagraphdijkstra
Miles
Miles

Reputation: 2537

Dijkstra Algorithm method returning empty path

I have attempted to implement Dijkstra's algorithm from the Pseudocode on the Wikipedia page. I have set a condition after the Queue is polled that tests if the current node is the target node, b. If so, then the Algorithm is to break and return the path from a to b.

This condition will always be satisfied as I know that all nodes within the range of the Adjacency Matrix do indeed exist. The program is to model the connections of the London Underground map.

Anyway, I have been trying to figure this out for a while now, and thus far it eludes me. Maybe somebody can spot the issue. Oh, adj is just the adjacency matrix for my graph.

    /**
   Implementation of Dijkstra's Algorithm taken from "Introduction to 
   Algorithms" by Cormen, Leiserson, Rivest and Stein. Third edition.

   d = Array of all distances.
   pi = Previous vertices.
   S = Set of vertices whose final shortest path weights have been
   determined.
   Q = Priority queue of vertices.
**/
public ArrayList<Integer> dijkstra(Integer a, Integer b){
    final double[] d = new double[adj.length];
    int[] pi = new int[adj.length];
    HashSet<Integer> S = new HashSet<Integer>();
    PriorityQueue<Integer> Q = new PriorityQueue<Integer>(d.length, new Comparator<Integer>(){
            public int compare(Integer a, Integer b){
                Double dblA = d[a-1];
                Double dblB = d[b-1];
                return dblA.compareTo(dblB);
            }
        });

    for(int i=0; i<d.length; i++){
        d[i] = Double.POSITIVE_INFINITY;
    }
    d[a] = 0f;
    for(int i=0; i<d.length; i++){
        Q.add(i+1);
    }

    while(Q.size() > 0){
        int u = Q.poll();
        if(u == b){
            System.out.println("jjd");
            ArrayList<Integer> path = new ArrayList<Integer>();
            for(int i=pi.length-1; i>=0; i--){
                path.add(pi[i]);
            }
            return path;
        }
        S.add(u);

        if(d[u] == Double.POSITIVE_INFINITY){
            break;
        }

        for(int v=0; v<adj.length; v++){
            double tmp = d[u] + adj[u][v];
            if(tmp < d[v]){
                d[v] = tmp;
                pi[v] = u;
            }
        }
    }
    return new ArrayList<Integer>();
}

}

EDIT:- After doing some debugging, it seems that the body of the while loop is being executed only once.

Upvotes: 2

Views: 885

Answers (2)

Daniel Fischer
Daniel Fischer

Reputation: 183968

    if(d[u] == Double.POSITIVE_INFINITY){
        break;
    }

    for(int v=0; v<adj.length; v++){
        double tmp = d[u] + adj[u][v];
        if(tmp < d[v]){
            d[v] = tmp;
            pi[v] = u;
        }
    }

The changing of the d values in the loop body doesn't rearrange the priority queue, so unless the element that happened to be at the top of the queue after popping the initial node is one of its neighbours, you will have d[u] == Double.POSITIVE_INFINITY in the next iteration and break then.

In Dijkstra's algorithm, it is important that the queue be updated when the distance of a node changes. java.util.PriorityQueue<E> doesn't offer that functionality, so using that is non-trivial, I see no way to use it other than removing and re-adding the updated nodes on every update. That is of course not very efficient, since removal is O(size).

The inefficiency can be mitigated by not having all nodes in the queue. Star with adding only the initial node, and in the loop, insert only the neighbours not yet seen, remove and reinsert the neighbours that already are in the queue. That keeps the queue shorter, and makes removal cheaper on average.

For an efficient implementation, you would need a custom priority queue that allows faster (O(log size)?) update of priorities.

Upvotes: 2

Wald
Wald

Reputation: 1091

If you get 'jjd' outputted in the console when you run the program from your System.out.println your problem should be this:

         if(u == b){
            System.out.println("jjd");
            ArrayList<Integer> path = new ArrayList<Integer>();
            for(int i=pi.length-1; i>=0; i--){
                path.add(pi[i]);
            }
            return path;

When you are calling the 'return path;' you actually break the whole method and return 'path'.

Upvotes: 0

Related Questions