Issue in Implementing Dijkstra's algorithm

Question

I am trying to solve a problem where I need to find the max distance between 2 points in a graph. I wrote this code for implementing Dijkstra's algorithm (obviously by changing the minimization to maximization), but it doesn't seem to work in some cases, and I am unable to figure out the unhandled case. Can anyone help me in pointing out what am I missing in my implementation or if something is inherently incorrect?

public double maxDistance(int n, int start, int end) {
    
    Map<Integer, List<Integer>> adjacencyList = getAdjacencyList(); // Adj. list in form of HashMap 
    Map<String, Double> distanceMap = getDistanceMap(); // <Edge, Double> (value is distance)
    Queue<Integer> bfsQueue = new LinkedList<>(); // queue to do a BFS
    
    boolean[] visited = new boolean[n];
    double[] distance = new double[n];
    
    bfsQueue.add(start);
    
    while (!bfsQueue.isEmpty()) {
        int node = bfsQueue.poll();
        
        List<Integer> neighbors = adjacencyList.getOrDefault(node, new ArrayList<>());
        for (int neighbor: neighbors) {
            if (visited[neighbor]) continue;
            bfsQueue.add(neighbor);
            double edgeLength = distanceMap.get(new Edge(node, neighbor));
            double newLength = distance[node] + edgeLength;
            if (newLength > distance[neighbor]) {
                distance[neighbor] = newLength;
            }
        }
        visited[node] = true;
    }

    return distance[end];
}

bfsQueue should probably be a priority queue, or some other sorted data structure, but not just a LinkedList. — cello
– cello, Commented Jan 16, 2021 at 8:45
also, without knowing the implementation of e.g. Edge, it's hard to judge if distanceMap.get(new Edge(...)) works as expected. Did you correctly overwrite Edge.equals() and Edge.hashCode()? — cello
– cello, Commented Jan 16, 2021 at 8:46
@cello I think that might be the issue. How does a sorted data structure make a difference here, can you please elaborate! — Ufder
– Ufder, Commented Jan 16, 2021 at 8:52
@Henry I’m typing from my phone so I’ll post the example when I’m home. — Ufder
– Ufder, Commented Jan 16, 2021 at 8:53

cello · Accepted Answer · 2021-01-16 09:12:34Z

1

First, Dijkstra's algorithm finds the shortest path, thus it should be minDistance, not maxDistance.

Next, to implement a breadth-first search, you need a sorted data structure. Your bfsQueue is currently just a LinkedList. With a linked list, you iterate over the items in the order of insertion. But in Dijkstra's algorithm it is important to always handle the next nearest neighbor. It is thus usually implemented with a priority queue.

As example why this makes a difference: Image you want to go from A to B. There are two routes available, a long one consisting of two edges, and a shorter one consisting of 4 edges. In your case, you basically expand through the graph by the number of edges since the start, and not by the distance. So you would first find the route consisting of two edges, even if this is the slower one.

If you use a PriorityQueue, be alerted that reducing the distance/priority of a neighbor as you do it currently (if (newLength > distance[neighbor]) { distance[neighbor] = newLength; }) will not work, as the priority queue will not automatically re-sort. You'll have to first remove the neighbor from the priority queue, update the distance, and then re-insert it into the priority queue so it gets sorted into the right place.

answered Jan 16, 2021 at 9:12

cello

5,5063 gold badges26 silver badges30 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Ufder Over a year ago

Thanks! I am trying to solve a cost-savings problem (maximization problem) so I just want to use this algorithm by adding appropriate variation. Wrt the sorting, I get it that its a greedy algorithm, but if I am going to check all the nodes any-way, then how does it matter which order I go in? That is the part I am not clear on.

cello Over a year ago

you visit each vertex only once (--> boolean[] visited), so it must be in a greedy way, otherwise you just end up with a random path in your graph -- or you would have to reset the visited flag somehow, but then it's definitely no longer Dijkstra's algorithm.

Ufder Over a year ago

Gotcha! I think I get it, let me try it out and come back and mark this answer. Thanks!

Ufder Over a year ago

PrirorityQueue works perfectly, and makes sense as its a greedy algorithm, so the next node being selected with the queue is always the one with max priority. Thanks for the help!

Collectives™ on Stack Overflow

Issue in Implementing Dijkstra's algorithm

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related