# How to get all paths between to items

I have to compute all possible paths between two items from a list. Each item has two fields: its name and its neighbor's name.

I have to generate a list containing all items that would allow me to make a path between two particular items.

Imagine I have Item(A, B) and Item(A, C) and I am being asked for the solution from B to C. I have to return both Items as I can reach C from B by using both of them: B->A->C.

Note that I have no limit on the Items I need to reach a destination.

I have tried several solutions but none of them was successful. I know I have to use some kind of recursive function but I can't figure out how.

This is my Item class:

``````public class Item {
private String name;
private String neighbor;

public Item(String name, String neighbor){

this.name = name;
this.neighbor = neighbor;
}

//getters and setters
}
``````

As I have to obtain all possible paths between two particular items, I have to return a list of lists:

``````List<List<Item>> solution;
``````

## My workaround

I finally converted my items to a Graph and, once it is build, I use Depth First Transversal (DFT) in order to find all possible paths between a source and a destination.

I set key-value pairs relating each Item's name with a graph representation and, from the Graph I get a list of Integers that indicates the path in the graph (1-2-3-5, for instance). From that list I find my Items and I return a list of lists with the format I've already explained.

Posting just for someone with a similar problem!

On

Try something like this based on my comment:

you could iterate over each node and perform a depth-first search on each node to see if you can reach the desired node

You mark visited nodes both to avoid cycles (if they're even possible in your use-case) and to track the path.

``````List<Item> depthFirstSearch(Item startItem, Item desiredItem, List<Item> visitedNodes) {
if (startItem.equals(desiredItem)) {
return visitedNodes;
}

// Exit if we reach a cycle or no more neighbors to follow
if (visitedNodes.contains(startItem) || startItem.getNeighbor() == null) {
return null;
}

// Recurse; continue search from neighbor
return depthFirstSearch(startItem.getNeighbor(), desiredItem, visitedNodes);
}
``````

And use it like this (You'll need to adapt this to your code):

``````List<Item> items;
List<List<Item>> result = new List<List<Item>>();

for (Item item : items) {
List<Item> pathToDesired = depthFirstSearch(item, desiredItem, new LinkedList<Item>());

if (pathToDesired != null) {
`result` will contain all paths to the desired item.