I have a table of with ids & their neighbors and need to create a recursive function that finds all possible paths from the start id to the end id without crossing the the same points twice. Lets assume the start id is 1 and the end id is 3.
{1 | 2,5}
{2 | 1,3,4,5}
{3 | 2,5}
{4 | 2}
{5 | 1,2,3}
This current snippet written by @Jeffrey Phillips Freeman worked pretty well, except that it only returns one possible path instead of all the possible paths which would be (1,2,3) & (1,5,3). I've been advised that an A* algorithm would work best for this situation, but I would still like to create the list of valid paths that take me from point A to B without going that route. The new snippet would need to simply place all the valid paths in an ArrayList. I intend to use the ArrayList to determine the best path by considering both the path length as well as other factors. So an ArrayList sorted by path distance would be a bonus. As an added note the nodes in the actual problem have spatial coordinates attached to them, however the path between nodes are not always straight lines.
List<Integer> searchHops(int from, int to, List<Integer> seen) {
seen.add(from);
if (from == to)
return new ArrayList<Integer>(Arrays.asList(from));
for (int neighbor : getNeighbors(from))
if (!seen.contains(neighbor)) {
List<Integer> result = searchHops(neighbor, to, seen);
if (result != null) {
result.add(0, from);
return result;
}
}
return null;
}
I have about 200 points and in it's current state, a simple test from point A to point B (only one point away) takes me on a 22 hop journey.
You can modify my original code to return all paths as a List just as you requested. Just dont have the code return early. This will not sort by path length, however, If you want that then you need A*.
public List<List<Integer>> searchHops(int from, int to, Set<Integer> seen) {
seen.add(from);
if (from == to) {
final List<List<Integer>> newList = new ArrayList<>();
newList.add(new ArrayList<>(Arrays.asList(from)));
return newList;
}
List<List<Integer>> allPaths = null;
for (int neighbor : getNeighbors(from)) {
if (!seen.contains(neighbor)) {
List<List<Integer>> results = searchHops(neighbor, to, new HashSet<>(seen));
if (results != null) {
for(List<Integer> result : results) {
result.add(0, from);
if( allPaths != null )
allPaths.add(result);
}
if( allPaths == null )
allPaths = results;
}
}
}
return allPaths;
}
If you actually care about ordering your paths from shortest path to longest path then it would be far better to use A*. A* will return as many of the possible paths as you want in order of shortest path first. So if what you really want are all possible paths ordered from shortest to longest then you still want the A* algorithm. The code I suggested above would be much slower than it needs to be if you care about ordering from shortest to longest, not to mention would take up more space then you'd want in order to store every possible path at once.
Since you indicated you cared about shortest path first, and may want to retrieve N-shortest paths then you absolutely should be using A* here.
If you want an A* based implementation capable of returning all paths ordered from the shortest to the longest, the following will accomplish that. It has several advantages. First off it is efficient at sorting from shortest to longest. Also it computes each additional path only when needed, so if you stop early because you dont need every single path you save some processing time. It also reuses data for subsequent paths each time it calculates the next path so it is more efficient. Overall should be the most efficient algorithm if you care about sorting by path length.
import java.util.*;
public class AstarSearch {
private final Map<Integer, Set<Neighbor>> adjacency;
private final int destination;
private final NavigableSet<Step> pending = new TreeSet<>();
public AstarSearch(Map<Integer, Set<Neighbor>> adjacency, int source, int destination) {
this.adjacency = adjacency;
this.destination = destination;
this.pending.add(new Step(source, null, 0));
}
public List<Integer> nextShortestPath() {
Step current = this.pending.pollFirst();
while( current != null) {
if( current.getId() == this.destination )
return current.generatePath();
for (Neighbor neighbor : this.adjacency.get(current.id)) {
if(!current.seen(neighbor.getId())) {
final Step nextStep = new Step(neighbor.getId(), current, current.cost + neighbor.cost + predictCost(neighbor.id, this.destination));
this.pending.add(nextStep);
}
}
current = this.pending.pollFirst();
}
return null;
}
protected int predictCost(int source, int destination) {
return 0; //Behaves identical to Dijkstra's algorithm, override to make it A*
}
private static class Step implements Comparable<Step> {
final int id;
final Step parent;
final int cost;
public Step(int id, Step parent, int cost) {
this.id = id;
this.parent = parent;
this.cost = cost;
}
public int getId() {
return id;
}
public Step getParent() {
return parent;
}
public int getCost() {
return cost;
}
public boolean seen(int node) {
if(this.id == node)
return true;
else if(parent == null)
return false;
else
return this.parent.seen(node);
}
public List<Integer> generatePath() {
final List<Integer> path;
if(this.parent != null)
path = this.parent.generatePath();
else
path = new ArrayList<>();
path.add(this.id);
return path;
}
@Override
public int compareTo(Step step) {
if(step == null)
return 1;
if( this.cost != step.cost)
return Integer.compare(this.cost, step.cost);
if( this.id != step.id )
return Integer.compare(this.id, step.id);
if( this.parent != null )
this.parent.compareTo(step.parent);
if(step.parent == null)
return 0;
return -1;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Step step = (Step) o;
return id == step.id &&
cost == step.cost &&
Objects.equals(parent, step.parent);
}
@Override
public int hashCode() {
return Objects.hash(id, parent, cost);
}
}
/*******************************************************
* Everything below here just sets up your adjacency *
* It will just be helpful for you to be able to test *
* It isnt part of the actual A* search algorithm *
********************************************************/
private static class Neighbor {
final int id;
final int cost;
public Neighbor(int id, int cost) {
this.id = id;
this.cost = cost;
}
public int getId() {
return id;
}
public int getCost() {
return cost;
}
}
public static void main(String[] args) {
final Map<Integer, Set<Neighbor>> adjacency = createAdjacency();
final AstarSearch search = new AstarSearch(adjacency, 1, 4);
System.out.println("printing all paths from shortest to longest...");
List<Integer> path = search.nextShortestPath();
while(path != null) {
System.out.println(path);
path = search.nextShortestPath();
}
}
private static Map<Integer, Set<Neighbor>> createAdjacency() {
final Map<Integer, Set<Neighbor>> adjacency = new HashMap<>();
//This sets up the adjacencies. In this case all adjacencies have a cost of 1, but they dont need to. Otherwise
//They are exactly the same as the example you gave in your question
addAdjacency(adjacency, 1,2,1,5,1); //{1 | 2,5}
addAdjacency(adjacency, 2,1,1,3,1,4,1,5,1); //{2 | 1,3,4,5}
addAdjacency(adjacency, 3,2,1,5,1); //{3 | 2,5}
addAdjacency(adjacency, 4,2,1); //{4 | 2}
addAdjacency(adjacency, 5,1,1,2,1,3,1); //{5 | 1,2,3}
return Collections.unmodifiableMap(adjacency);
}
private static void addAdjacency(Map<Integer, Set<Neighbor>> adjacency, int source, Integer... dests) {
if( dests.length % 2 != 0)
throw new IllegalArgumentException("dests must have an equal number of arguments, each pair is the id and cost for that traversal");
final Set<Neighbor> destinations = new HashSet<>();
for(int i = 0; i < dests.length; i+=2)
destinations.add(new Neighbor(dests[i], dests[i+1]));
adjacency.put(source, Collections.unmodifiableSet(destinations));
}
}
The output from the above code is the following:
[1, 2, 4]
[1, 5, 2, 4]
[1, 5, 3, 2, 4]
Notice that each time you call nextShortestPath() it generates the next shortest path for you on demand. It only calculates the extra steps needed and doesnt traverse any old paths twice. Moreover if you decide you dont need all the paths and end exeuction early you've saved yourself considerable computation time. You only compute up to the number of paths you need and no more.
If you have some sort of a heuristic that helps you estimate path cost then override the predictCost() method and put it there. You mentioned that your nodes also have spatial coordinates associated with them. A good heuristic in this case would be the euclidean distance between the two nodes (the distance a straight line between them would be). It is however entirely option and only helps improve computation time if you exit before computing all possible paths.
Finally it should be noted that the A* and Dijkstra algorithms do have some minor limitations, though I dont think it would effect you. Namely it will not work right on a graph that has negative weights.
Here is a link to JDoodle where you can run the code yourself in the browser and see it working. You can also change around the graph to show it works on other graphs as well: http://jdoodle.com/a/ukx