BFS - properties

Hi there,

i’m trying to understand the bfs properties(last one) which is described here

can anyone explain . thanks in advance :slight_smile:

Find the shortest path of even length from a source vertex s
to a target vertex t in an unweighted graph: For this, we must construct an auxiliary graph, whose vertices are the state (v,c), where v - the current node, c=0 or c=1 - the current parity. Any edge (a,b) of the original graph in this new column will t<urn into two edges ((u,0),(v,1)) and ((u,1),(v,0)). After that we run a BFS to find the shortest path from the starting vertex (s,0) to the end vertex (t,0).

2 Likes

The idea is that normal BFS would yield the shortest path, odd or even. Since we are interested in the shortest ‘even’ length path only, we need to ensure that our algorithm keeps track of the parity of the distance of each vertex from the source. We would like BFS to continue looking for an even length path even if has already visited the vertex on a shorter odd-length path. This is done by splitting each vertex v into v0 and v1. A path from s0 (s is source vertex) to v0 denotes an even length path from source to vertex v in the original graph. The edges in this modified graph are between vertices of opposite parities only, and these edges correspond to those in the given graph.
Here’s my implementation for the same. It’s much easier to explain in code.

/* Shortest path of even length */

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

#define pb push_back

vector<vector<int> > adj;

int main() {
int n;  cin >> n;
int m;  cin >> m;
adj.resize(2 * n);  // (0 .. n-1) parity 0 && (n .. 2n-1) parity 1 
for (int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v;
    adj[u].pb(v + n), adj[v + n].pb(u);
    adj[u + n].pb(v), adj[v].pb(u + n);
}
int s, t;
cin >> s >> t;
queue<int> q;
bool vis[2*n];
q.push(s);  vis[s] = true;
vector<int> d(2*n, 1e9 + 9);
d[s] = 0;
while (!q.empty()) {    // path from s --> t implicitly defines path from s0 to t0
    int u = q.front();    q.pop();
    for (auto v : adj[u]) {
        if (!vis[v]) {
            q.push(v);
            vis[v] = true;
            d[v] = d[u] + 1;
        }
    }
}
cout << d[t] << endl;
return 0;
}
/*
Input : 5 vertices (0 to 4), 6 edges
Source 0, Target 2

5 6
0 1
0 2
1 3
2 3
2 4
3 4
0 2

*/
1 Like

bro i didn’t get you…

We split every node into 2. Node ‘u’ gets split into ‘u’ and’u+n’. Node u denotes node u but with even number of steps, and node u+n denotes u, but with odd number of steps.So if there’s a edge from u to v, We create the edges

u    -> v+n
u+n  -> v
v    -> u+n
v+n  -> u

These just denote going from even u to odd v, going from odd u to even v, etc.
You have to find the shortest path to even x.

2 Likes

thank you bro@everrule1

@everule1 @divyanshhardia any practise problem u have??

Could you plz explain a concept