How to make my path-finding algorithm not go in reverse?

Question

My path-finding method is given two objects containing an id, name, x/y coordinates, and path stored in an Array List. The path data is the id of each object that it can directly connect to. The objective is to call my method recursively until it finds its goal using the shortest distance, and when it reaches the end it returns true.

The problem: If the distance to the node that you came from is shorter than the other nodes in the current nodes path, then it will cause an infinite loop bouncing back and forth between the two nodes. I have struggled with this problem for several hours and could be over thinking it. Any advice or suggestions will be greatly appreciated!

The Algorithm:

while (!pathfound) {
    current = findPath(current, end);
}

public static Place findPath(Place curPlace, Place endPlace) {
    ArrayList<Integer> path = curPlace.path;
    int id;
    double lastdist = 999;
    double distance;
    Place bestPlace = null;

    for (int i = 0; i < path.size(); i++) {
        id = curPlace.path.get(i);
        distance = distance(getPlace(id), curPlace)
                + distance(getPlace(id), endPlace);
        if (distance < lastdist) {
            bestPlace = getPlace(id);
        } 

        lastdist = distance;
    }

    if (result.length() == 0) {
        result += bestPlace.name;
    } else {
        result += ", " + bestPlace.name;
    }

    System.out.println("CURCITY: " + bestPlace.id);
    System.out.println(result);
    System.out.println(lastdist);

    if (bestPlace == endPlace) {
        pathfound = true;
    }

    return bestPlace;
}

You can ignore result, it is for keeping up with the nodes that are passed through. If there are any other details you would like to know, please ask.

Answer 1

If it is acceptable to modify Place you can add a boolean "visited" flag. Reset them all to false prior to running the algorithm; set to true when you visit and false when you leave (don't forget to unset them on the way out of the recursion - if you do this properly you can even avoid having to explicitly reset the flags before starting). Skip nodes where the flag is true.

A more short-sighted option is to pass the last visited Place as a parameter to the function, and skip that one. This will not prevent larger loops but may be entirely appropriate for your situation and is the simplest to implement.

Both of the above are O(1) with minimal overhead. If you cannot modify Place you could store a Set of visited places (remove them from the set on the way out of recursion), and skip places that are already in that set. Depending on your performance requirements, if you use a HashSet you will want to come up with an appropriate hashing function.

Along those lines, at the expense of more memory, if your ID numbers are unique and cover a reasonably sized finite range, a boolean[] indexed by ID number is a constant time alternative to a set here (it is essentially the "visited" flag option with the flags stored externally).