Infinite recursion java issue

Question

I am trying to solve a problem and can't seem to figure this one out. I have tried creating Lists and sets that keep track of the towns visited and then to skip if it is already visited but none of my implementations have worked so far.

The problem is, given a graph with routes such as AB5 it implies a route from town A to B with a distance of 5. Now given the input AB5, BC4, CD8, DC8, DE6, AD5, CE2, EB3, AE7 I am trying to find the shortest path from B to B. The answer should be 9.

I have seen that the problem exists because the recursion checks path C to D and then checks all D's paths. D contains a route to C to then it goes to C and that is where the infinite recursion happens. How can I implement a check to make sure it does not go round the C to D and D to C routes infinitely.

This is my coded function for this problem:

public int shortestDistance(char startTown, char endTown, char currentTown, int distance, int step) {
        if (currentTown == endTown && step != 0) {
            return distance;
        }

        int shortestDistance = Integer.MAX_VALUE;
        for (char nextTown : graph.get(currentTown).keySet()) {
            shortestDistance = Math.min(shortestDistance, shortestDistance(startTown, endTown, nextTown,
                    distance + graph.get(currentTown).get(nextTown), step + 1));
        }
        return shortestDistance;
    }

Answer 1

This is probably Dijkstra's alogrithm for finding shortest path and as per your code there is no way to keep track of the nodes which are already visited. So this will lead to infinite recusrion in case if there's a cycle in the graph. To solve this simply keep a visited structure. Something like:

/*
Set<Character> visited parameter: keeps track of the nodes that have already been visited.
So, before checking a node the function checks if it's in the visited set. 
If it is, the function skips it. If it's not, the function adds it to the visited set and checks it.
*/
public int shortestDistance(char startTown, char endTown, char currentTown, int distance, int step, Set<Character> visited) {
    if (currentTown == endTown && step != 0) {
        return distance;
    }

    visited.add(currentTown);

    int shortestDistance = Integer.MAX_VALUE;
    for (char nextTown : graph.get(currentTown).keySet()) {
        if (!visited.contains(nextTown)) {
            shortestDistance = Math.min(shortestDistance, shortestDistance(startTown, endTown, nextTown,
                    distance + graph.get(currentTown).get(nextTown), step + 1, visited));
        }
    }

    visited.remove(currentTown);

    return shortestDistance;
}