I recently had to solve a problem that involved finding the shortest path between two vertices (or nodes). A DuckDuckGo search suggested that an algorithm called breadth-first search was the way to go. Here’s an implementation in Java, based on chapter 22 in Introduction to Algorithms by Cormen et al. Source on GitHub.

First let’s come up with an example graph we can work with. I’m using the same example as the book, the below graph with 5 vertices and 7 edges. Let’s say we want the shortest path from 1 to 3.

In order to model the graph, we’ll need a representation of a vertex.

public class Vertex {
    private int id;
    private List edges = new ArrayList<>();
    private boolean discovered;
    private Vertex predecessor;
    private Integer distance;

    // getters and setters omitted
}

The first two instance variables hold an id, allowing us to identify the vertex, and a list of edges, allowing us to model the relationship between this vertex and those it is connected to.

As we traverse the vertices in the graph, we’ll want to know weather or not we have already discovered a vertex, so we don’t end up in a loop where we keep finding the same vertices over and over again.

Once we’ve found our goal vertex, how do we find the path back to the source? By letting each vertex save a reference to its predecessor. That way starting with our goal vertex, we can keep asking vertices for their predecessors until we get to the source.

Finally we’re saving the distance to the source node. This isn’t strictly necessary, but we might want to know what it is.

Now that we have a way to model our vertices, we can create an example graph and implement the algorithm. See the ExampleGraph class on GitHub for the Java implementation of the graph above.

public class BreadthFirstSearch {

    List<Vertex> getPathToGoal(Vertex source, Vertex goal) {
        Queue<Vertex> queue = new LinkedList<>();
        queue.add(source);

        while (!queue.isEmpty()) {
            Vertex current = queue.remove();

            System.out.println("Vertex " + current.getId() + " at distance " + current.getDistance());

            if (current.getId() == goal.getId()) {
                return getPath(current);
            }

            for (Vertex vertex : current.getEdges()) {
                if (!vertex.isDiscovered()) {
                    vertex.setDiscovered(true);
                    vertex.setDistance(current.getDistance() + 1);
                    vertex.setPredecessor(current);
                    queue.add(vertex);
                }
            }

        }
        return null;
    }

    private List<Vertex> getPath(Vertex vertex) {
        List<Vertex> path = new ArrayList<>();

        while (vertex != null) {
            path.add(vertex);
            vertex = vertex.getPredecessor();
        }
        Collections.reverse(path);
        return path;
    }
}

The algorithm can be described as follows. First create a queue containing the source vertex. Then repeat the following until either the goal is found, or there are no more vertices.

  1. Take a vertex from the front of the queue.
  2. Check if the vertex is the goal.
    1. If it is the goal, return a path to the goal.
    2. If it’s not the goal, get the edges of the vertex, add them to the queue and start over.

Let’s run the program and check the result.

public static void main(String[] args) {
    BreadthFirstSearch bfs = new BreadthFirstSearch();
    Map<Integer, Vertex> vertices = ExampleGraph.init();

    Vertex source = vertices.get(1);
    source.setAsRootNode();
    Vertex goal = vertices.get(3);

    List path = bfs.getPathToGoal(source, goal);

    System.out.print("Shortest path from " + source.getId() + " to " + goal.getId() + ":");
    for (Vertex vertex : path) {
        System.out.print(" " + vertex.getId());
    }
}

This prints:

Vertex 1 at distance 0
Vertex 2 at distance 1
Vertex 5 at distance 1
Vertex 4 at distance 2
Vertex 3 at distance 2
Shortest path from 1 to 3: 1 2 3