Day 32 | BFS to Find Shortest Path in Graph | C++

Yesterday, we got started with graphs. I am very for this series because the graphs are beautiful. Once you get to understand them, you will fall in love with them because they involve some of the most creative and beautiful solutions you will find in Competitive Programming.

Before we get started with the topic, I want to make sure that we are all on the same page by explaining what is the shortest path.

Shortest Path

In graphs, there can be multiple paths to reach node B from node A, a path that includes the minimum number of intermediate edges is called the shortest path, they can be multiple in numbers.

Consider this graph -

Here there are 2 paths to reach 7 from 3

• 3 - 2 - 1- 6 - 7

• 3 - 2 - 6 - 7

The length of the first path is 4 because there are 4 edges in the path,

similarly, the length of the second path is 3

Why do so much hardwork to find shortest path?

Graphs are everywhere in the IT world and shortest path algorithms are required regularly, some common examples are -

• Map Applications - Cities are vertices and roads are edges. Of course, you want to travel on the shortest path (Either shortest by sum, or traffic maxima).

• Internet - Your internet is a network of computers as well. A shorter path would help you reach your packets faster, thus faster internet.

• Friends Network - Let's say you are asking for referrals from your friends or asking them to ask their friends, you would want the closest one to give a referral.

Okay, so will we learn those scary algorithms now?

Scary? Are you asking about Djikstra and Bellman-Ford Algorithms? They are not scary, just need a little practice to understand.

Today we will just be solving shortest path problems with our own Breadth-First Search Algorithm.

Let's have a recap with the example we discussed last time, Breadth-first search will start from grandfather, then your aunts and uncles, and then your generation. Your grandfather is at a distance of 0 from his generation, Aunts, and Uncles are 1 generation away from your grandfather's generation and hence you peeps are 2 generations away.

So basically we will be going to the closest distance first and then the distance is increasing gradually. So each vertex when visited, will be visited at the shortest distance possible.

We can just add distance vector to pre-existing code and we are done

Pre-existing code

void bfs(int start, vector<vector<int>> &graph){
    list<int> in_queue; 
    vector<bool> visited ( graph.size() );
    in_queue.push_back(start);
    visited[start] = true;
    while(in_queue.size()){
        int u = in_queue.front();
        cout << u << " ";
        in_queue.pop_front();
        for(int v : graph[u]){
            if(visited[v])continue;
            visited[v] = true;
            in_queue.push_back(v);
        }
    }
}

Shortest path calculating code

vector<int> bfs(int start, vector<vector<int>>& graph){
    list<int> in_queue; 
    vector<bool> visited ( graph.size() );
    vector<int> distance ( graph.size() );
    in_queue.push_back(start);
    visited[start] = true;
    distance[start] = 0; // Because start is 0 steps away from start
    while(in_queue.size()){
        int u = in_queue.
        in_queue.pop_front();
        for(int v : graph[u]){
            if(visited[v])continue;
            visited[v] = true;
            distance[v] = distance[u] + 1;
            in_queue.push_back(v);
        }
    }
    return distance;
}

Let's solve a Fight Against Traffic now

Now we know that BFS can get us the shortest path, then we can just get the distance between all pairs of vertices and check the count. Like this

/*
This code will give time limit exceeded
*/

#include<bits/stdc++.h>
using namespace std;

int n,m;
vector<vector<int>> g;

int bfs(int start, int dest){
    vector<int> distance (n + 1);
    vector<int> vis (n + 1);
    list<int> in_queue;
    vis[start] = 0;
    distance[start] = 0;
    in_queue.push_back(start);
    while(in_queue.size()){
        int u = in_queue.front();
        in_queue.pop_front();
        for(int v : g[u]){
            if(vis[v])continue;
            vis[v] = true;
            distance[v] = distance[u] + 1;
            in_queue.push_back(v);
        }
    }
    return distance[dest];
}

int main(){
    cin >> n >> m;
    g = vector<vector<int>> (n + 1);
    int start, dest;
    cin >> start >> dest;
    set<pair<int,int>> included_in_graph;
    while(m--){
        int a,b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
        included_in_graph.insert({a,b});
        included_in_graph.insert({b,a});
    }
    int initial_distance = bfs(start,dest);
    int count = 0;
    for(int A = 1; A <= n; A++){
        for(int B = A + 1; B <= n; B++){
            if(included_in_graph.count({A,B}))
                continue;
            g[A].push_back(B);
            g[B].push_back(A);
            
            int new_distance = bfs(start, dest);
            if(new_distance == initial_distance)
                count++;
            g[A].pop_back();
            g[B].pop_back();
        }
    }
    cout << count << "\n";
}

But a single run of BFS has the complexity of O(V+E) when using an adjacency list.

There are O(N^2) pairs.

And V+E = 2*N (here)

Thus complexity will be O(N^3), BFS * pairs.

N being of order 1000, O(N^3) will have 10^9 operations order, it should be 10^8 for 1 second.

Thus this approach does not work.

So what we can do is -

Imagine we are trying to add edge {A, B} which is not in the graph and we want to check if this will decrease the shortest distance between start and end or not.

Distance between start and end can be either (depending on which is closer to what)

• Distance (start, A) + 1 (new edge between A and B) + Distance (B, end)

• Distance (start, B) + 1 (new edge between A and B) + Distance (A, end)

Notice that if a new edge reduces distance, then this must be the path because all paths not using A, and B (initial graph) are already accounted for when calculating the shortest path initially.

Hence we can implement it like this

#include<bits/stdc++.h>
using namespace std;

int n,m;
vector<vector<int>> g;

vector<int> bfs(int source){
    vector<int> distance (n + 1);
    vector<bool> vis (n + 1);
    list<int> in_queue;
    vis[source] = true;
    distance[source] = 0;
    in_queue.push_back(source);
    while(in_queue.size()){
        int u = in_queue.front();
        in_queue.pop_front();
        for(int v : g[u]){
            if(vis[v])continue;
            vis[v] = true;
            distance[v] = distance[u] + 1;
            in_queue.push_back(v);
        }
    }
    return distance;
}

int main(){
    cin >> n >> m;
    g = vector<vector<int>> (n + 1);
    int start, dest;
    cin >> start >> dest;
    set<pair<int,int>> included_in_graph;
    while(m--){
        int a,b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
        included_in_graph.insert({a,b});
        included_in_graph.insert({b,a});
    }
    vector d_start = bfs(start);
    vector d_dest = bfs(dest);
    int init_distance = d_start[dest];
    int count = 0;
    for(int A = 1; A <= n; A++){
        for(int B = A + 1; B <= n; B++){
            if(included_in_graph.count({A,B}))
                continue;
            int distance1 = d_dest[A] + d_start[B] + 1;
            int distance2 = d_start[A] + d_dest[B] + 1;
            if(distance1 >= init_distance && distance2 >= init_distance){
                count++;
            }
        }
    }
    cout << count << "\n";
}

Please like and share my posts if they are helpful.