Shortest path in an unweighted graph in C++

In an unweighted graph from a source to the destination, we may have several paths. We have to find out the shortest path among all in C++. Let’s have an example:

Our graph be like:
               
                            4
                          / | \
                     0---3  |  2
                          \ | /
                            1

In this graph suppose source is 0 and destination is 4.

So, we have following three paths:
        0 -> 3 -> 4
        0 -> 3 -> 1 -> 4
        0 -> 3 -> 1 -> 2 -> 4

Among the three paths the shortest is :   0 -> 3 -> 4

Shortest Path in an Unweighted Graph

Approach:

We’ll use the concept of breadth-first search (mostly known as BFS). In BFS, we traverse the breadth at first. Here, we will have a parent array that keeps track of parents for all the adjacents. While traversing, for a popped vertex when we’ll check for the adjacents, we’ll set that popped vertex as the parent for all the adjacents. As we are doing BFS, the values of the parent array will be set in such a way that we’ll get the shortest path when we’ll trace the path from destination to source in parent array.

At first, we will do BFS and that sets the parent array as well as returns whether the destination is reachable or not from that source. If the destination is not reachable it prints that. Otherwise, using the parent array we trace the path from destination to source but we have to print this in reverse order. So, we will use a stack to arrange the path. We’ll push the path in the stack while tracing the path in parent array. This is how the path will be reversed and printed from source to destination.

 

Class to represent the graph:

// class to represent a graph.
class graph {
    
    private:
        int v;
        vector<int> *adj;

    public:
        // constructor.
        graph(int v) {
            this->v = v;
            adj = new vector<int> [v];
        }

        // set all the edges.
        void add_edge(int u, int v) {
            adj[u].push_back(v);
            adj[v].push_back(u);
        }

        void print_path(int source, int dest);
        bool BFS(int source, int dest, int parent[]);
};

 

Function to print the shortest path:

This function calls another function named as BFS. If the return value of BFS says that destination is reachable then it prints the path.

// function to print the shortest path.
void graph::print_path(int source, int dest) {

    // it stores parent for each vertex to trace the path.
    int parent[v];

    // BFS returns false means destination is not reachable.
    if(BFS(source, dest, parent) == false) {
        cout << "Destination is not reachable from this source.\n";
        return;
    }

    // stack to store the shortest path.
    stack<int> st;

    // tracing the path.
    while(parent[dest] != -1) {
        st.push(dest);
        dest = parent[dest];
    }

    // printing the path.
    cout << source;
    while(!st.empty()) {
        cout << " -> " << st.top();
        st.pop();
    }

    return;
}

 

Function for traversal:

// this function returns if destination is reachable or not
// additionally it sets the parent array to say the path (if exist).
bool graph::BFS(int source, int dest, int parent[]) {

    queue<int> q;
    bool visited[v];

    // setting all the vertices as non-visited
    // and parents of all vertices as -1.
    for(int i=0; i<v; i++) {
        visited[i] = false;
        parent[i] = -1;
    }

    // pushing the source into the queue and mark it as visited.
    q.push(source);
    visited[source] = true;

    // loop executes until all vertices are traversed.
    while(!q.empty()) {

        // popping one element from queue.
        int temp = q.front();
        q.pop();

        // check for all adjacents.
        for(int k: adj[temp]) {
            if(visited[k] == false) {
                
                // pushing into queue and mark it visited as well as
                // set the parent of the adjacent in parent array.
                q.push(k);
                visited[k] = true;
                parent[k] = temp;

                // if destination is reached, returns true
                // to state that there exist a path.
                if(k == dest)
                    return true;
            }
        }
    }

    // if destination is not reachable.
    return false;
}

 

Driver function for Input 1:

// driver function.
int main() {

    // sample graph.
    graph g(6);

    g.add_edge(0, 3);
    g.add_edge(3, 1);
    g.add_edge(3, 4);
    g.add_edge(1, 4);
    g.add_edge(2, 4);
    g.add_edge(1, 2);

    g.print_path(0, 4);

    return 0;
}

 

Output 1:

    0 -> 3 -> 4

 

Driver function for Input 2:

// driver function.
int main() {

    // sample graph.
    graph g(6);

    g.add_edge(0, 3);
    g.add_edge(3, 1);
    g.add_edge(3, 4);
    g.add_edge(1, 4);
    g.add_edge(2, 4);
    g.add_edge(1, 2);

    g.print_path(0, 5);

    return 0;
}

 

Output 2:

    Destination is not reachable from this source.

 

Time Complexity:

  • This is simply the breadth-first traversal of a graph. So, the complexity will be O(V+E), where V is the number of vertices and E is the number of edges.

Leave a Reply

Your email address will not be published. Required fields are marked *