Right now you're not accounting for the possibility that there may be multiple paths from the baseIndex to the searchIndex - presumably you want the shortest path if this is the case. One way to correct for this is to replace the nested for loops with a single for loop around a recursive call. Return Integer.MAX_VALUE
if a path isn't found, then if your shortest path has a count of Integer.MAX_VALUE
then you'll know that you weren't able to find a path. (If you DID find a path with a count of Integer.MAX_VALUE
then something probably went wrong with your path-finding algorithm - you shouldn't have paths that are that long.) If you want to use nested loops instead of recursion then you can convert the recursive call into a loop by using your own stack variable.
public int searchGraph(int baseIndex, int searchIndex, int count) {
if(baseIndex == searchIndex) {
return count;
} else if(count > indexToIndecies.size()) {
return Integer.MAX_VALUE; // cycle in graph
} else {
int returnVal = Integer.MAX_VALUE;
for(int i = 0; i < indexToIndecies.get(baseIndex).size(); i++) {
int temp = searchGraph(indexToIndecies.get(baseIndex).get(i), searchIndex, count + 1);
returnVal = temp < returnVal ? temp : returnVal;
}
return returnVal;
}
}
This should return the shortest path, and if it returns Integer.MAX_VALUE
then a path wasn't found.
Another option is to return an Integer
instead of an int
, in which case you can return a null in the case that you couldn't find a path.
Edit: SimonC pointed out in the comments that a cycle in the graph could cause a stack overflow. I've corrected for this by returning Integer.MAX_VALUE
if count
exceeds indexToIndecies.size()
, since count
shouldn't exceed the number of keys in the map.