Infinite loop in Dijkstra algorithm?

Question

I'm trying to implement the Dijkstra algorithm to find the shortest path between two intersections (vertices) in a graph. Unfortunately, I am getting an infinite loop in the while loop and I can't really figure out why.

NodeDist is a hashmap between intersections and doubles, and finds the distance between nodes in the graph. Distance is determined by the length of the 'street' (edges) in the graph. Previous is a hashmap that keeps track of intersections to intersections, namely, the intersection that was looked at before the intersection we are looking at now.

public List<IntersectionI> dijkstraPath(IntersectionI start, IntersectionI end){
    ArrayList<IntersectionI> path = new ArrayList<IntersectionI>();
    Iterator<IntersectionI> it = graph.myGraph.keySet().iterator();
    //Initializing all unvisited node distances as infinity.
    while (it.hasNext()){
        IntersectionI next = it.next();
        nodeDist.put(next, INFINITY);
    }
    //Remove the start node, put in 0 distance. 
    nodeDist.remove(start);
    nodeDist.put(start, (double) 0);
    queue.add(start);
    //computes paths
    while (!queue.isEmpty()){
        IntersectionI head = queue.poll();
        if (nodeDist.get(head) == INFINITY)
            break;
        visited.put(head, true);
        List<StreetI> str = head.getStreetList();
        for (StreetI e : str){
            Point pt1 = e.getFirstPoint();
            Point pt2 = e.getSecondPoint();
            IntersectionI p1 = graph.pointGraph.get(pt1);
            IntersectionI p2 = graph.pointGraph.get(pt2);
            if (head.getLocation().equals(p1)){
                double dist = e.getDistance();
                double addedDist = nodeDist.get(start)+dist;
                double p2Dist = nodeDist.get(p2);
                if (addedDist < p2Dist){
                    previous.put(p2, head);
                    Point p22 = p2.getLocation();
                    p22.setCost(addedDist);
                    nodeDist.put(p2, addedDist);
                    queue.add(p2);
                }

            }
            else {
                double dist = e.getDistance();
                double addedDist = nodeDist.get(start)+dist;
                if (addedDist < nodeDist.get(p1)){
                    previous.put(p1, head);
                    Point p11 = p1.getLocation();
                    p11.setCost(addedDist);
                    nodeDist.put(p1, addedDist);
                    queue.add(p1);
                }
            }
        }
    }
    //gets shortest path
    for (IntersectionI vertex = end; vertex != null; vertex = previous.get(vertex))
        path.add(vertex);
    System.out.println("ya");
    Collections.reverse(path);
    return path;
}

//The comparator that sorts by intersection distance.
public class distCompare implements Comparator<IntersectionI> {
    @Override
    public int compare(IntersectionI x, IntersectionI y) {
        Point xPo = x.getLocation();
        Point yPo = y.getLocation();
        if (xPo.getCost() < yPo.getCost())
            return 1;
        else if (yPo.getCost() < xPo.getCost())
            return -1;
        else return 0;

    }
}

do streets go both ways? is a->b on the list, and b->a? it looks to me like you could get both, and each iteration would just add the other back on? -- update doesn't look the case, as you have a < (not <=) — John Gardner
The graph is undirected...does that mean I should have a <=? — user202925
I think there's a problem with double addedDist = nodeDist.get(start)+dist; and double addedDist = nodeDist.get(start)+dist;. Should it really be start? I think it should be head, right? — irrelephant
OH! Yeah making it 'head' removes the infinite loop error. Thanks for the help! — user202925

irrelephant irrelephant · Accepted Answer · 2012-12-11T01:12:35

So, this ended up solving the problem in the comments:

double addedDist = nodeDist.get(start)+dist;

should be

double addedDist = nodeDist.get(head)+dist;

both times.

The added distance should come from the current vertex, not the start vertex (the distance to which is 0).

Infinite loop in Dijkstra algorithm?

1 Answers