Day 35 | Actually Getting the Shortest Path | C++

Imagine, you open Google Maps and search for a location. And in return Maps tells you that it is 3 KM away. It is not very useful in most of the cases, you also want the directions. Similarly, there are tons of problems which require the actual path of graph.

When we earlier find shortest path, we were just interested in the length of shortest path. Today we will encounter some problems in which need directions or the actual path.

Some recap

Do you remember how we found the shortest path in unweighted graphs? It was using BFS and distance vector. We updated distance vector to be value 1 more than distance to the parent. Like this -

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;
}

Now, we can modify this code to actually get the path. But let's solve this problem in real life first.

Let's say you are in forest and since you can get lost you keep marking on trees about the where is previous tree you marked on like this

On Nth tree you marks where is N-1th tree

This way it is easier to find the place you started from.

Similarly, if you store the parents of vertices. You will know where you came from and you can then traceback to the source and mark vertices in between to get the path.

You can write BFS which stores parents as well like this

void bfs(int source){
    vis[source] = true;
    queue<int> q;
    q.push(source);
    while(q.size()){
        int u = q.front();
        q.pop();
        for(int v: g[u]){
            if(vis[v])continue;
            vis[v] = true;
            parent[v] = u;
            q.push(v);
        }
    }
}

​Learning Moment

Queues - They are very common data structure you will find in Computer Science. It actually has a simple job just like an actual queue that is to hold elements in a queue LOL.

What actually happens is you keep inserting elements into queue and then you can access only the first element inserted into the queue. When you delete that first element then you can access second element just like in queue when first person is done, then second person's chance comes

Hence using the queue in code above.

Let's Solve some problems then

Message Route

This is exactly the problem we discussed but we still need to get path right from parents vector.

You can do it like this

vector<int> path;
int current = n;
while(current > 0){
    path.push_back(current);
    current = parent[current];
}
reverse(path.begin(), path.end());
cout << path.size() << "\n";
for(int i : path )cout << i << " ";

Combining all, you can implement solution like this

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

const int N = 2e5 + 10;
vector<int> g[N];
bool vis[N];
int parent[N];

void bfs(int source){
    vis[source] = true;
    queue<int> q;
    q.push(source);
    while(q.size()){
        int u = q.front();
        q.pop();
        for(int v: g[u]){
            if(vis[v])continue;
            vis[v] = true;
            parent[v] = u;
            q.push(v);
        }
    }
}

int main(){
    int n,m;
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int a,b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    bfs(1);
    if(!vis[n]){
        cout << "IMPOSSIBLE\n";
        return 0;
    }

    vector<int> path;
    int current = n;
    while(current > 0){
        path.push_back(current);
        current = parent[current];
    }
    reverse(path.begin(), path.end());
    cout << path.size() << "\n";
    for(int i : path )cout << i << " ";
}

Labyrinth

We need to do similar thing but point as (i,j). Here the main challenge is printing the directional path that is ULRD format.

Once you get path, you can check for all i,i-1 pairs to see which direction we took from i-1 to reach i like this

/*
int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};
string direction = "UDLR";
*/
string ans = "";
for(int i = 1; i < path.size(); i++){
    pair<int,int> previous = path[i-1];
    pair<int,int> current = path[i];
    for(int dir = 0; dir < 4; dir++){
        pair<int,int> prev_next = make_pair(previous.first + dx[dir], previous.second + dy[dir]);
        if(prev_next == current){
            ans += direction[dir];
            break;
        }
    }
}

Combining this with previously learned ones, we can implement it like this

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

int n,m;
vector<string> a;
vector<vector<pair<int,int>>> parent;
vector<vector<bool>> vis;

int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};
string direction = "UDLR";

bool valid(int i, int j){
    if(i >= 0 && i < n && j >= 0 && j < m && a[i][j] != '#' && !vis[i][j])
        return true;
    return false;
}

void bfs(int source_i, int source_j){
    vis[source_i][source_j] = true;
    queue<pair<int,int>> q;
    parent[source_i][source_j] = make_pair(-1,-1);
    q.push(make_pair(source_i, source_j));

    while(q.size()){
        int i,j;
        tie(i,j) = q.front();
        q.pop();
        for(int dir = 0; dir < 4; dir++){
            int next_i = i + dx[dir];
            int next_j = j + dy[dir];

            if(!valid(next_i, next_j))
                continue;

            vis[next_i][next_j] = true;
            q.push(make_pair(next_i, next_j));
            parent[next_i][next_j] = make_pair(i,j);

        }
    }
}

int main(){
    cin >> n >> m;
    a = vector<string> (n);
    parent = vector<vector<pair<int,int>>> (n, vector<pair<int,int>> (m));
    vis = vector<vector<bool>> (n, vector<bool> (m));

    for(auto &i : a)cin >> i;
    int start_i, start_j, end_i, end_j;
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(a[i][j] == 'A')
                start_i = i, start_j = j;
            if(a[i][j] == 'B')
                end_i = i, end_j = j;
        }
    }
    
    bfs(start_i,start_j);

    if(!vis[end_i][end_j]){
        cout << "NO";
        return 0;
    }
    // To mark ending

    vector<pair<int,int>> path;
    
    while(end_i >= 0 && end_j >= 0){
        path.emplace_back(end_i, end_j);
        int p_i = parent[end_i][end_j].first;
        int p_j = parent[end_i][end_j].second;
        end_i = p_i;
        end_j = p_j;
    }

    reverse(path.begin(), path.end());

    cout << "YES\n" << path.size() - 1 << "\n";
    string ans = "";
    for(int i = 1; i < path.size(); i++){
        pair<int,int> previous = path[i-1];
        pair<int,int> current = path[i];
        for(int dir = 0; dir < 4; dir++){
            pair<int,int> prev_next = make_pair(previous.first + dx[dir], previous.second + dy[dir]);
            if(prev_next == current){
                ans += direction[dir];
                break;
            }
        }
    }
    cout << ans;
}

Please like and share my posts if they are helpful.