Find The Shortest Path Between Vertices In A Graph

In the previous post we implemented an algorithm that checks if there is a path between two vertices in a graph. In this post we are going to implement an algorithm that finds the shortest path between two vertices in a graph.

The ProblemPermalink

Given a graph $G$ return the smallest total number of edges between two vertices $a$ and $b$ – the shortest path between the two vertices. If no path exists, return $-1$.

SolutionPermalink

To solve this problem we are going to use breadth first traversal. However, instead of just storing the vertices in our queue we are going to store a tuple that contains a vertex and its distance from the source vertex (the number of edges between them). As we enqueue a vertex’s neighbors we should just make sure to increment the distance so that every neighbor has 1 more distance value than the current vertex. If we find the destination vertex then we just return the distance value. The time complexity for this algorithm is $O(n + k)$ where $n$ is the number of vertices and $k$ is the number of edges in the graph. The space complexity is $O(n)$. The code is similar to the one we used to check if there is a path between two vertices. Here it is:

public int GetShortestPath(T source, T destination)
{
    if (!_adjacentList.ContainsKey(source) || !_adjacentList.ContainsKey(destination))
    {
        return -1;
    }
    Queue<(T Vertex, int Distance)> queue = new();
    HashSet<T> visited = new();
    queue.Enqueue((source, 0));

    while (queue.Count > 0)
    {
        var (vertex, distance) = queue.Dequeue();
        if (vertex.CompareTo(destination) == 0)
        {
            return distance;
        }

        if (!visited.Contains(vertex))
        {
            visited.Add(vertex);
            foreach (var neigbor in _adjacentList[vertex])
            {
                queue.Enqueue((neigbor, distance + 1));

        }
    }
    return -1;
}

In this post we implemented an algorithm that finds the shortest path (if it exists) between two vertices in a graph. All the code is available on GitHub if you want to check it out. Till next time thanks so much for taking your time to read.