Shortest Path in an Unweighted Graph Using BFS

Shortest path algorithms are designed to find the minimum cost path between two nodes in a graph.
For example, a shortest path algorithm can be used to find the fastest route between two places or the minimum number of connections required to reach one point from another.
An unweighted graph is a graph in which all the edges are of same cost. Therefore, the shortest path is simply the path with the minimum number of edges.
The easiest way to find the shortest path in an unweighted graph is by using BFS (Breadth First Search).
Before going ahead, you can have a look at Graph Basics if you are not familiar with graph representation..

Why BFS Finds the Shortest Path

BFS (Breadth First Search) visits graph nodes level by level. Starting from the source node:

• nodes directly connected to the source are visited first.
• then nodes at distance 2.
• then nodes at distance 3.
• and so on.

Since all edges in an unweighted graph have the same cost, the first time BFS reaches a node, will be the shortest path to that node.

Algorithm

• Define a distance array of size equal to graph node and initialize it to -1.
• Define a path array of size equal to graph node and initialize it to -1.
• Pick the given graph node to start the traversal and enqueue it into a Queue.
• Set the distance for the start node as 0 and path to reach from itself.
• Dequeue the node from the Queue.
  • For all the edge from the dequeued node, if distance of any neighbor node is set to “-1” then
    •  set distance = distance[dequeued node] + 1
    • Put this neighbor node in queue.
    • Update path[neighbor] = dequeued_node
• Repeat above step till the queue is empty.

The distance array tells us how far each node is from the source.
The path array can be used to reconstruct the actual shortest path.

Implementation

Let’s look into a sample Graph class which we are going to use it here. Check Graph and it’s basic implementation for more details.

class Graph
{
    private:
        int m_nodes;
        int m_edges;
        int **edges;
        bool isUndirected;
        int isConnected;

    public:
        Graph (int nodes, bool isUndirected);
        int getNumberOfNodes ();
        int getNumberOfEdges ();
        void getEdges ();
        bool addEdge (int srcNode, int dstNode);
        ~Graph ();
        void shortestPathInUnweightedGraph (int srcNode);
};

Let’s look into the function to find shortest path in unweighted graph. Please look into Queue and It’s implementation before going ahead.

void Graph::shortestPathInUnweightedGraph (int srcNode)
{
    int distance[m_nodes];
    int path[m_nodes];
    for (int i = 0; i < m_nodes; i++) {
        distance[i] = -1;
        path[i] = -1;
    }

    Queue q(m_nodes);
    q.enqueue (srcNode);
    distance[srcNode] = 0;
    path[srcNode] = srcNode;

    while (!q.isEmpty ()) {
        int cur_node = q.dequeue ();
        if (distance[cur_node] == -1) {
            cout << "Incorrect distance set for node: " << cur_node << endl;
        }
        for (int j = 0; j < m_nodes; j++) {
            if (edges[cur_node][j] == 1 && distance[j] == -1) {
                distance[j] = distance[cur_node] + 1;
                q.enqueue (j);
                path[j] = cur_node;
            }
        }
    }
    for (int i = 0; i < m_nodes; i++) {
        cout <<"Node: " << i << " distance: " << distance[i] << " from Node: " << path[i] << endl;
    }
}

We use distance[node] == -1 to identify whether a node has already been visited.
Once a node is discovered, its shortest distance is:

distance[neighbour] = distance[currentNode] + 1

We also store the current node as its parent:

parent[neighbour] = currentNode

This parent information can later be used to reconstruct the complete shortest path.

Example Graph

Let’s look into an unweighted graph in which we have to calculate the shortest path to all the vertices from a given node.

Let’s define the sample graph shown above and check how this code works.

int main ()
{
    Graph g2(11, true);
    g2.addEdge (0,4);
    g2.addEdge (1,0);
    g2.addEdge (6,0);
    g2.addEdge (1,2);
    g2.addEdge (1,5);
    g2.addEdge (2,3);
    g2.addEdge (6,3);
    g2.addEdge (3,7);
    g2.addEdge (4,8);
    g2.addEdge (5,8);
    g2.addEdge (9,7);
    g2.addEdge (8,9);
    g2.addEdge (9,10);
    g2.getEdgesIn2DFormat ();
    g2.topologicalSort ();
    add_header ("Finding shortest path from Node 6");
    g2.shortestPathInUnweightedGraph (6);
    add_header ("Finding shortest path from Node 0");
    g2.shortestPathInUnweightedGraph (0);
}

Let’s check the output of above code.

Printing edges in 2D format!!
0  1  0  0  1  0  1  0  0  0  0
1  0  1  0  0  1  0  0  0  0  0
0  1  0  1  0  0  0  0  0  0  0
0  0  1  0  0  0  1  1  0  0  0
1  0  0  0  0  0  0  0  1  0  0
0  1  0  0  0  0  0  0  1  0  0
1  0  0  1  0  0  0  0  0  0  0
0  0  0  1  0  0  0  0  0  1  0
0  0  0  0  1  1  0  0  0  1  0
0  0  0  0  0  0  0  1  1  0  1
0  0  0  0  0  0  0  0  0  1  0
========================================================================
Finding shortest path from Node 6
========================================================================
Node: 0 distance: 1 from Node: 6
Node: 1 distance: 2 from Node: 0
Node: 2 distance: 2 from Node: 3
Node: 3 distance: 1 from Node: 6
Node: 4 distance: 2 from Node: 0
Node: 5 distance: 3 from Node: 1
Node: 6 distance: 0 from Node: 6
Node: 7 distance: 2 from Node: 3
Node: 8 distance: 3 from Node: 4
Node: 9 distance: 3 from Node: 7
Node: 10 distance: 4 from Node: 9
========================================================================
Finding shortest path from Node 0
========================================================================
Node: 0 distance: 0 from Node: 0
Node: 1 distance: 1 from Node: 0
Node: 2 distance: 2 from Node: 1
Node: 3 distance: 2 from Node: 6
Node: 4 distance: 1 from Node: 0
Node: 5 distance: 2 from Node: 1
Node: 6 distance: 1 from Node: 0
Node: 7 distance: 3 from Node: 3
Node: 8 distance: 2 from Node: 4
Node: 9 distance: 3 from Node: 8
Node: 10 distance: 4 from Node: 9

Finding the Actual Shortest Path

The distance array tells us the length of the shortest path.
If we also want the actual path, we can follow the parent array backwards from the destination node.

For example, if the parent information is:

10 -> 9
9  -> 7
7  -> 3
3  -> 6

then the shortest path from node 6 to node 10 is:

6 -> 3 -> 7 -> 9 -> 10

Time Complexity

BFS time complexity is O(V + E) where V = number of Vertices and E = Number of Edges.
However, the sample implementation above uses an adjacency matrix and checks every possible neighbor for each node.
Therefore, this above implementation takes: O(V²)

For large sparse graphs, an adjacency-list representation is generally more efficient.

Space Complexity

The additional arrays and queue require: O(V) extra spaces.

Summary

For an unweighted graph, BFS is the simplest way to find the shortest path.
The main idea is:

• start BFS from the source node;
• assign distance 0 to the source;
• every newly discovered node gets distance[parent] + 1;
• store the parent of each node if the actual path is required.

Since BFS explores nodes level by level, the first path found to any node is also the shortest path in an unweighted graph.