Returning the path in Dijkstra's Algorithm

Question

So, I've been implementing Dijkstra's algorithm for pathfinding through a maze I generate (I know some of you might think something like A* would be better, but Dijkstra's perfectly fits my needs), and I've run into a small issue. I feel like I'm overlooking something, but when I return the "path" from the start node to the end node, it returns the entire search path the algorithm took (every node it visited), and not the path to the node.

//Uses djikstra's algorithm to find the shortest path between two nodes
//"vertices" is the global ArrayList in the class with all vertices in the graph.
@Override
public ArrayList<Vertex> pathfind(Vertex v1, Vertex v2) {
    ArrayList<Vertex> path = new ArrayList<Vertex>();
    ArrayList<Vertex> unvisited = new ArrayList<Vertex>();
    ArrayList<Vertex> visited = new ArrayList<Vertex>();

    if (!vertices.contains(v1) || !vertices.contains(v2)) {
        return path;
    }

    //initialize distances
    v1.setDistance(0);
    for(Vertex vert : vertices) {
        if(vert != v1) {
            vert.setDistance(Integer.MAX_VALUE);
        }
        unvisited.add(vert);
    }
    Vertex current = v1;

    //begin
    while (!unvisited.isEmpty()) {  
        //for all adjacent vertices that are unvisited
        for (Vertex v : current.adjacentVertices()) {
            if (!visited.contains(v)) {
                //if the distance of that vertex is greater than 
                //the added distance of the current node + the edge connecting the two
                int pathDist = current.getDistance() + findEdge(current, v).getElement(); 
                if (v.getDistance() > pathDist) {
                    //assign the new distance
                    v.setDistance(pathDist);
                }
            }
        }

        //remove the current node from the visited set and add it to visited
        visited.add(current);
        unvisited.remove(current);

        //add current node to the path
        path.add(current);

        //return if we found the destination
        if (current == v2)) {
            return path;
        }

        //else move to the lowest value node
        current = findSmallest(unvisited);

    }
    return path;

}

I know it must be something painfully obvious but I'm hitting my head against the wall, any help would be appreciated. Thanks!

Is there a reason you used current.equals(v2) instead of current == v2? This appears to be a case where you want ==, since you want to see if you're at the same vertex, not whether the data in the vertex is equal (if you overrode equals). I doubt that this is the cause of your problem, though. — ajb
@ajb Each vertex has a coordinate value, and .equals checks if the coordinates are equal. You have a good point, but either one would work. — Jeremy Robertson
Actually, if equals has been overridden for Vertex, then you cannot use contains. — ajb
Oops, thanks! I'll correct that. The issue with the path persists though, it's probably unrelated — Jeremy Robertson
You're adding current to path every time you add it to visited. You'll want to add some condition there... — adamdc78

nitishagar nitishagar · Accepted Answer · 2014-12-18T01:55:54

You might want to calculate the distances first/ stabilize the distance to minimum value using the algo, then run over the graph to get the nodes for the path.

As current = findSmallest(unvisited) might get you node from a path which is not connected.

Returning the path in Dijkstra's Algorithm

2 Answers