0-1 BFS Algorithm

Introduction to 1-0 BFS

In this Tutorial, we will discuss 0-1 BFS. BFS is a prerequisite for this blog. If you don’t know how BFS works, learn it Breadth First Search Algorithm (BFS).
And read the single source shortest path in an unweighted graph ( Single Source Shortest Path in an Unweighted Grap ).

In the single source shortest path problem, if the given graph is unweighted then we can use BFS. The time complexity of this approach is O(V+E) where V is the number of vertex and E is the number of edges.
But if the graph is weighted then BFS will now work. In this case, we have to use the Dijkstra algorithm. The time complexity of the Dijkstra algorithm is O(ElogV) or O(V² + E). In an unweighted graph, we can also use Dijkstra.
However, if the graph has only two types of weight, 0 and 1, we can apply the Dijkstra algorithm. But the better approach is using modified BFS which is faster than the Dijkstra algorithm.

In traditional BFS, we maintain a queue. In 0-1 BFS we will maintain a deque. When we go to a node using an edge if the edge cost is 1 we will put this node at the back of the deque. And if the edge cost is 0 we will put it at the front of the deque. All other step is similar to BFS.

Let’s discuss this with an example.
Suppose we have a graph below.

We want to find the shortest path from node 1 to node 3. The shortest path has the least cost. And the cost of a path is the sum of the cost of the edges of the path.
one path from node 1 to node 3 is 1 -> 5 -> 0 -> 2 -> 3. The cost of this path is 3.

Finding the shortest path in this graph is similar to finding the shortest path in an unweighted graph that we discussed here. We will use a deque instead of a queue.

0-1 BFS in C++

#include<bits/stdc++.h>
 
using namespace std;
 
int main()
{
    int n,m;
    cin>>n; // n is the number of vertices
    cin>>m; // m is the number of edges
    vector<vector<int> > adj(n); // n vector for each node
    vector<vector<int> > cost(n);
 
    // input edgelist
    for(int i=0;i<m;i++)
    {
        int a, b, c;
        cin>>a>>b>>c;
        adj[a].push_back(b);
        adj[b].push_back(a);
        cost[a].push_back(c);
        cost[b].push_back(c);
    }
    int source, destination;
    cin>>source; // input source node
    cin>>destination; // input destination node
    vector<int> visited(n), parent(n);
    deque<int> q;
    q.push_back(source);
    visited=1;
    parent=source;
    while(!q.empty())
    {
        int r=q.front();
        q.pop_front();
        for(int i=0;i<adj[r].size();i++)
        {
        	auto it=adj[r][i];
            if(visited[it]==0)
            {
            	if(cost[r][i]==1)
            		q.push_back(it);
            	else
            		q.push_front(it);
            	visited[it]=1;
            	parent[it]=r;
            }
        }
    }
    if(visited[destination]==0)
    {
    	cout<<"There is no path between node "<<source<<" to "<<destination<<endl;
    	return 0;
    }
    vector<int> path;
    path.push_back(destination);
    while(parent[path.back()]!=path.back())
    {
    	path.push_back(parent[path.back()]);
    }
 	reverse(path.begin(),path.end());
 	for(auto it:path)
 	{
 		cout<<it<<" ";
 	}
 	cout<<endl;
    return 0;
}

This is an implementation of the 1-0 BFS algorithm in C++. The 1-0 BFS algorithm is used to find the shortest path between two nodes in a weighted graph with only two edge weights, 0 and 1. The algorithm is similar to BFS, but instead of using a queue, it uses a deque to store the nodes. The deque is used to keep track of nodes at distance 0 and nodes at distance 1 from the source node.

The input consists of the number of vertices, number of edges, the edgelist with each edge represented as (u, v, w) where u and v are the endpoints and w is the weight, the source node, and the destination node.

The algorithm starts by initializing the visited and parent arrays with 0 and the source node respectively. A deque is used to store the nodes, with the source node being pushed to the back of the deque. The while loop runs until the deque is empty. For each node in the deque, the algorithm checks its adjacent nodes. If an adjacent node has not been visited before, it is added to the deque with a push_back operation if the weight of the edge connecting the current node and the adjacent node is 1, or a push_front operation if the weight is 0. The visited and parent arrays are updated accordingly.

If the destination node is not visited, it means there is no path between the source and destination nodes. Otherwise, the path is reconstructed by starting at the destination node and following the parent array until the source node is reached. The path is stored in a vector and printed in reverse order to obtain the correct order of the nodes from the source to the destination.

0-1 BFS in Python

from collections import deque 
adj=[]
cost=[]
n=int(input()) # number of vertices.
m=int(input()) # number of edges
 
 
for i in range(n):
    adj.append([])
    cost.append([])
 
 
# input edge list.
for i in range(m):
    a, b, c=map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)
    cost[a].append(c)
    cost[b].append(c)

source=int(input()) # input source node
destination=int(input()) # input destination node

path=[]     
 
dq=deque()
visited=[0 for i in range(n)]
parent=[0 for i in range(n)]
visited=1
parent=source
while dq:
    r=dq[0]
    dq.popleft()
    for i in range(len(adj[r])):
        if visited[adj[r][i]]==0:
            visited[adj[r][i]]=1
            if cost[r][i]==1:
            	dq.append(adj[r][i])
            else:
            	dq.appendleft(adj[r][i])
            parent[adj[r][i]]=r 


path.append(destination)
while parent[path[-1]]!=path[-1]:
	path.append(parent[path[-1]])

path=path[::-1]
print(path)

This code implements the 1-0 BFS algorithm to find the shortest path between two nodes in an undirected graph with non-negative edge weights. The algorithm uses a deque data structure to maintain a list of unexplored nodes, with nodes at the front having a distance of 0, and nodes at the back having a distance of 1.

The code starts by taking input for the number of vertices and edges in the graph. It then initializes an adjacency list and a cost list with empty lists for each vertex. The adjacency list will hold the neighbors of each vertex, and the cost list will hold the weight of each edge between vertices.

Next, the code takes input for the source and destination nodes. It then initializes a deque with the source node, sets the visited and parent arrays to 0 for all vertices, and sets the visited and parent arrays for the source node.

The main part of the algorithm is implemented in the while loop. The loop continues as long as there are nodes to explore in the deque. At each iteration, it pops the node at the front of the deque, r, and explores its neighbors. For each neighbor, if it has not been visited yet, the code sets its visited status to 1 and sets its parent to r. It then appends or prepends the neighbor to the deque depending on the weight of the edge between r and the neighbor. If the weight is 1, it appends the neighbor to the deque, and if the weight is 0, it prepends the neighbor to the deque.

Once the while loop completes, the code checks if the destination node was visited. If it was not, it prints a message saying there is no path between the source and destination nodes. Otherwise, it initializes an empty path list and adds the destination node to it. It then iterates over the parent array, adding each parent to the path list until it reaches the source node. Finally, it reverses the path list and prints it as the shortest path between the source and destination nodes.