# Find all paths in a graph

A few years back I was tasked with an interesting problem for a coding interview. Given a cyclic graph I had to find all possible paths from a starting node to a destination node. The graph was weighted and I also had to provide a method to find the shortest path. At first I thought to focus on finding all the available paths, then I could simply filter out all the results and return the shortest path. That’s what I am going to do in this implementation. I’ll cover the **Dijkstra** implementation in another post.

Here is what the graph looks like:

The circles represents the nodes, the arrows represents the direction of a connection and the number on the arrows represents the weight. Interesting to note, node *D* and node *E* are bi-directional. I am going to solve this problem with a *BFS* approach using a *Queue*. *Breadth First Search* is a recursion technique where neighbours nodes in a tree or a graph are explored before children nodes, I have briefly covered them in this article.
Let’s talk about the solution before we jump into the implementation. I am going to use a *Queue* data structure which follows *FILO* (first in last out). Say for instance we have a queue of integer with only a single entry with the value `1`

.

Now we want to add the value `2`

, the value will be added at the end of the collection.

If was to poll that queue now I would get `1`

and the queue would be remaining with only the value `2`

.

What I want to do in this implementation is to poll the queue until it is not empty and if the last node in the path is not the destination, then I want to explore the neighbours and add to the queue a new list that includes previous nodes and the current neighbour node.
When I finally find a complete path, I will add that to a list and continue traversing until the graph has been completely explored. I am trying to find all paths from node `A`

to node `C`

. During the first iteration the queue will contain:

Polling the queue gives me back a list containing `A`

since that’s not my destination node, I will start exploring `A`

’s neighbours `B`

and `D`

adding two new lists including the previous node and the new neighbours *[[A, B], [A, D]]*.

Polling the queue now gives me back a list containing *A* and *B*, since *B* is not the destination node, I will go through the same routine above and start exploring all of `B`

’s neighbours. The queue will now contain: *[[A, D], [A, B, C], [A, B, E]]*.

Polling the queue now gives me back a list containing *A* and *D*, since *D* is not the destination node, I will go through the same routine above and start exploring all of `D`

’s neighbours. The queue will now contain: *[[A, B, C], [A, B, E] [A, D, C], [A, D, E]]*.

Polling the queue now gives me back a list containing *A*, *B* and *C*, *C* is the destination node, therefore I save this path and keep polling the queue.

Hopefully this explanation was easy to follow. Here is how I have implemented my solution. I first created four different classes:

The *Node* represents a node in the graph.

The *Edge* represents the connection between two nodes in the graph with the weight.

The *Path* represents a path as a list of edges.

The *Graph* represents the graph as an adjacency list and implements methods to find all paths and the shortest path. The following is the logic for finding all the paths in the graph. In order to accomodate for easily query the lenght of a path, I wrote a little for loop that helps me with building the list of edges that is required for building the `Path`

. Something worth noticing is that this solution works well with non cyclic graphs, to avoid incurring in an infinite recursion and a *StackOverflowError* I have added a check where if a path contains the same element more than once, it is discarded since nodes can only be visited one time.

As I previously stated in this post, in order to find the shortest path, I have decided to simply reduce the list of paths to a single path with the shortest distance. The implementation looks like the following:

Running the following test will help validating the solution.

The complete source code for the snippets illustrated in this post can be found in the java-series repo.