Open In App

0-1 BFS (Shortest Path in a Binary Weight Graph)

Last Updated : 17 Apr, 2024
Improve
Improve
Like Article
Like
Save
Share
Report

Given a graph where every edge has weight as either 0 or 1. A source vertex is also given in the graph. Find the shortest path from the source vertex to every other vertex. 

For Example: 

Input : Source Vertex = 0 and below graph Having vertices like(u,v,w):
      Edges: [[0,1,0], [0, 7, 1], [1,2,1], [1, 7, 1], [2, 3, 0], [2, 5, 0], [2, 8, 1], [3, 4, 1],[3, 5, 1],[4, 5, 1],[5, 6, 1],[6, 7, 1],[7, 8, 1]] 


Output : Shortest distances from given source
         0 0 1 1 2 1 2 1 2

Explanation : 
Shortest distance from 0 to 0 is 0
Shortest distance from 0 to 1 is 0
Shortest distance from 0 to 2 is 1
..................

A simple way to find ne­arby nodes is called 0-1 BFS. Instead of marking visite­d nodes with a boolean array, it checks a condition at e­ach step. It uses a double-e­nded queue to store­ nodes. If an edge has a we­ight of 0, the node is inserte­d at the front of the queue­. But if the edge has a we­ight of 1, the node goes at the­ back.

This method is similar to Dijkstra’s algorithm. It updates the shorte­st distance to a node based on its ne­ighboring nodes. A node is added to the­ queue only if its distance could be­ improved by the previous node­’s distance. This helps find the optimal path to re­ach nodes.

This way works well in many case­s. When taking a point from the line (like­ Dijkstra’s way), it means that point has the smallest we­ight left. If there is a ne­xt point with weight 0, it is the same distance­ as the point just taken. But if the ne­xt point has weight 1, it is now the farthest away of all points still in the­ line. This is because all othe­r points either connect straight to the­ current point or connect to points already take­n.
 

C++ 
// C++ program to implement single source
// shortest path for a Binary Graph
#include<bits/stdc++.h>
using namespace std;

/* no.of vertices */
#define V 9

// a structure to represent edges
struct node
{
    // two variable one denote the node
    // and other the weight
    int to, weight;
};

// vector to store edges
vector <node> edges[V];

// Prints shortest distance from given source to
// every other vertex
void zeroOneBFS(int src)
{
    // Initialize distances from given source
    int dist[V];
    for (int i=0; i<V; i++)
        dist[i] = INT_MAX;

    // double ende queue to do BFS.
    deque <int> Q;
    dist[src] = 0;
    Q.push_back(src);

    while (!Q.empty())
    {
        int v = Q.front();
        Q.pop_front();

        for (int i=0; i<edges[v].size(); i++)
        {
            // checking for the optimal distance
            if (dist[edges[v][i].to] > dist[v] + edges[v][i].weight)
            {
                dist[edges[v][i].to] = dist[v] + edges[v][i].weight;

                // Put 0 weight edges to front and 1 weight
                // edges to back so that vertices are processed
                // in increasing order of weights.
                if (edges[v][i].weight == 0)
                    Q.push_front(edges[v][i].to);
                else
                    Q.push_back(edges[v][i].to);
            }
        }
    }

    // printing the shortest distances
    for (int i=0; i<V; i++)
        cout << dist[i] << " ";
}

void addEdge(int u, int v, int wt)
{
   edges[u].push_back({v, wt});
   edges[v].push_back({u, wt});
}

// Driver function
int main()
{
    addEdge(0, 1, 0);
    addEdge(0, 7, 1);
    addEdge(1, 7, 1);
    addEdge(1, 2, 1);
    addEdge(2, 3, 0);
    addEdge(2, 5, 0);
    addEdge(2, 8, 1);
    addEdge(3, 4, 1);
    addEdge(3, 5, 1);
    addEdge(4, 5, 1);
    addEdge(5, 6, 1);
    addEdge(6, 7, 1);
    addEdge(7, 8, 1);
    int src = 0;//source node
    zeroOneBFS(src);
    return 0;
}
Java 
// Java Program to implement 0-1 BFS
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;

public class ZeroOneBFS {
    private static class Node {
        int to; // the ending vertex
        int weight; // the weight of the edge
        
        public Node(int to, int wt) {
            this.to = to;
            this.weight = wt;
        }
    }
    
    private static final int numVertex = 9;
    private ArrayList<Node>[] edges = new ArrayList[numVertex];
    
    public ZeroOneBFS() {
        for (int i = 0; i < edges.length; i++) {
            edges[i] = new ArrayList<Node>();
        }
    }
    
    public void addEdge(int u, int v, int wt) {
        edges[u].add(edges[u].size(), new Node(v, wt));
        edges[v].add(edges[v].size(), new Node(u, wt));
    }
    
    public void zeroOneBFS(int src) {

        // initialize distances from given source
        int[] dist = new int[numVertex];
        for (int i = 0; i < numVertex; i++) {
            dist[i] = Integer.MAX_VALUE;
        }
        
        // double ended queue to do BFS
        Deque<Integer> queue = new ArrayDeque<Integer>();
        dist[src] = 0;
        queue.addLast(src);
        
        while (!queue.isEmpty()) {
            int v = queue.removeFirst();
            for (int i = 0; i < edges[v].size(); i++) {

                // checking for optimal distance
                if (dist[edges[v].get(i).to] > 
                        dist[v] + edges[v].get(i).weight) {

                    // update the distance
                    dist[edges[v].get(i).to] =
                          dist[v] + edges[v].get(i).weight;

                    // put 0 weight edges to front and 1
                    // weight edges to back so that vertices
                    // are processed in increasing order of weight
                    if (edges[v].get(i).weight == 0) {
                        queue.addFirst(edges[v].get(i).to);
                    } else {
                        queue.addLast(edges[v].get(i).to);
                    }
                }
            }
        }
        
        for (int i = 0; i < dist.length; i++) {
            System.out.print(dist[i] + " ");
        }
    }
    
    public static void main(String[] args) {
        ZeroOneBFS graph = new ZeroOneBFS();
        graph.addEdge(0, 1, 0);
        graph.addEdge(0, 7, 1);
        graph.addEdge(1, 7, 1);
        graph.addEdge(1, 2, 1);
        graph.addEdge(2, 3, 0);
        graph.addEdge(2, 5, 0);
        graph.addEdge(2, 8, 1);
        graph.addEdge(3, 4, 1);
        graph.addEdge(3, 5, 1);
        graph.addEdge(4, 5, 1);
        graph.addEdge(5, 6, 1);
        graph.addEdge(6, 7, 1);
        graph.addEdge(7, 8, 1);
        int src = 0;//source node
        graph.zeroOneBFS(src);
        return;
    }
}
Python3 
# Python3 program to implement single source
# shortest path for a Binary Graph
from sys import maxsize as INT_MAX
from collections import deque

# no.of vertices
V = 9

# a structure to represent edges
class node:
    def __init__(self, to, weight):

        # two variable one denote the node
        # and other the weight
        self.to = to
        self.weight = weight

# vector to store edges
edges = [0] * V
for i in range(V):
    edges[i] = []

# Prints shortest distance from 
# given source to every other vertex
def zeroOneBFS(src: int):

    # Initialize distances from given source
    dist = [0] * V
    for i in range(V):
        dist[i] = INT_MAX

    # double ende queue to do BFS.
    Q = deque()
    dist[src] = 0
    Q.append(src)

    while Q:
        v = Q[0]
        Q.popleft()

        for i in range(len(edges[v])):

            # checking for the optimal distance
            if (dist[edges[v][i].to] > 
                dist[v] + edges[v][i].weight):
                dist[edges[v][i].to] = dist[v] + edges[v][i].weight

                # Put 0 weight edges to front and 1 weight
                # edges to back so that vertices are processed
                # in increasing order of weights.
                if edges[v][i].weight == 0:
                    Q.appendleft(edges[v][i].to)
                else:
                    Q.append(edges[v][i].to)

    # printing the shortest distances
    for i in range(V):
        print(dist[i], end = " ")
    print()

def addEdge(u: int, v: int, wt: int):
    edges[u].append(node(v, wt))
    edges[u].append(node(v, wt))

# Driver Code
if __name__ == "__main__":

    addEdge(0, 1, 0)
    addEdge(0, 7, 1)
    addEdge(1, 7, 1)
    addEdge(1, 2, 1)
    addEdge(2, 3, 0)
    addEdge(2, 5, 0)
    addEdge(2, 8, 1)
    addEdge(3, 4, 1)
    addEdge(3, 5, 1)
    addEdge(4, 5, 1)
    addEdge(5, 6, 1)
    addEdge(6, 7, 1)
    addEdge(7, 8, 1)

    # source node
    src = 0
    zeroOneBFS(src)

# This code is contributed by
# sanjeev2552
C# 
// C# Program to implement 0-1 BFS
using System;
using System.Collections.Generic;

class ZeroOneBFS {
    private class Node {
        public int to; // the ending vertex
        public int weight; // the weight of the edge
        
        public Node(int to, int wt) {
            this.to = to;
            this.weight = wt;
        }
    }
    
    private const int numVertex = 9;
    private List<Node>[] edges = new List<Node>[numVertex];
    
    public ZeroOneBFS() {
        for (int i = 0; i < edges.Length; i++) {
            edges[i] = new List<Node>();
        }
    }
    
    public void addEdge(int u, int v, int wt) {
        edges[u].Add(new Node(v, wt));
        edges[v].Add(new Node(u, wt));
    }
    
    public void zeroOneBFS(int src) {
        // initialize distances from given source
        int[] dist = new int[numVertex];
        for (int i = 0; i < numVertex; i++) {
            dist[i] = int.MaxValue;
        }
        
        // double ended queue to do BFS
        Queue<int> queue = new Queue<int>();
        dist[src] = 0;
        queue.Enqueue(src);
        
        while (queue.Count > 0) {
            int v = queue.Dequeue();
            for (int i = 0; i < edges[v].Count; i++) {
                // checking for optimal distance
                if (dist[edges[v][i].to] > 
                        dist[v] + edges[v][i].weight) {

                    // update the distance
                    dist[edges[v][i].to] =
                          dist[v] + edges[v][i].weight;

                    // put 0 weight edges to front and 1
                    // weight edges to back so that vertices
                    // are processed in increasing order of weight
                    if (edges[v][i].weight == 0) {
                        queue.Enqueue(edges[v][i].to);
                    } else {
                        queue.Enqueue(edges[v][i].to);
                    }
                }
            }
        }
        
        for (int i = 0; i < dist.Length; i++) {
            Console.Write(dist[i] + " ");
        }
    }
    
    static void Main(string[] args) {
        ZeroOneBFS graph = new ZeroOneBFS();
        graph.addEdge(0, 1, 0);
        graph.addEdge(0, 7, 1);
        graph.addEdge(1, 7, 1);
        graph.addEdge(1, 2, 1);
        graph.addEdge(2, 3, 0);
        graph.addEdge(2, 5, 0);
        graph.addEdge(2, 8, 1);
        graph.addEdge(3, 4, 1);
        graph.addEdge(3, 5, 1);
        graph.addEdge(4, 5, 1);
        graph.addEdge(5, 6, 1);
        graph.addEdge(6, 7, 1);
        graph.addEdge(7, 8, 1);
        int src = 0;//source node
        graph.zeroOneBFS(src);
        return;
    }
}
// This code is contributed by Prajwal Kandekar
Javascript 
<script>
// Javascript Program to implement 0-1 BFS

class Node
{
    constructor(to,wt)
    {
        this.to = to;
            this.weight = wt;
    }
    
}

let numVertex = 9;
let edges = new Array(numVertex);

function _ZeroOneBFS()
{
    for (let i = 0; i < edges.length; i++) {
            edges[i] = [];
        }
}

function addEdge(u,v,wt)
{
    edges[u].push(edges[u].length, new Node(v, wt));
        edges[v].push(edges[v].length, new Node(u, wt));
}

function zeroOneBFS(src)
{
    // initialize distances from given source
        let dist = new Array(numVertex);
        for (let i = 0; i < numVertex; i++) {
            dist[i] = Number.MAX_VALUE;
        }
          
        // double ended queue to do BFS
        let queue = [];
        dist[src] = 0;
        queue.push(src);
          
        while (queue.length!=0) {
            let v = queue.shift();
            for (let i = 0; i < edges[v].length; i++) {
  
                // checking for optimal distance
                if (dist[edges[v][i].to] > 
                        dist[v] + edges[v][i].weight) {
  
                    // update the distance
                    dist[edges[v][i].to] =
                          dist[v] + edges[v][i].weight;
  
                    // put 0 weight edges to front and 1
                    // weight edges to back so that vertices
                    // are processed in increasing order of weight
                    if (edges[v][i].weight == 0) {
                        queue.unshift(edges[v][i].to);
                    } else {
                        queue.push(edges[v][i].to);
                    }
                }
            }
        }
          
        for (let i = 0; i < dist.length; i++) {
            document.write(dist[i] + " ");
        }
}

_ZeroOneBFS();
addEdge(0, 1, 0);
addEdge(0, 7, 1);
addEdge(1, 7, 1);
addEdge(1, 2, 1);
addEdge(2, 3, 0);
addEdge(2, 5, 0);
addEdge(2, 8, 1);
addEdge(3, 4, 1);
addEdge(3, 5, 1);
addEdge(4, 5, 1);
addEdge(5, 6, 1);
addEdge(6, 7, 1);
addEdge(7, 8, 1);
let src = 0;//source node
zeroOneBFS(src);

// This code is contributed by avanitrachhadiya2155
</script>

Output
0 0 1 1 2 1 2 1 2


This problem can also be solved by Dijkstra but the time complexity will be O(E + V Log V) whereas by BFS it will be O(V+E).
 



A

Ayush Jha
Improve
Previous Article
Karp's minimum mean (or average) weight cycle algorithm
Next Article
Find minimum weight cycle in an undirected graph

Similar Reads

Shortest Path in a weighted Graph where weight of an edge is 1 or 2
Given a directed graph where every edge has weight as either 1 or 2, find the shortest path from a given source vertex ‘s’ to a given destination vertex ‘t’. Expected time complexity is O(V+E). A Simple Solution is to use Dijkstra’s shortest path algorithm, we can get a shortest path in O(E + VLogV) time. How to do it in O(V+E) time? The idea is to
15 min read
Difference between the shortest and second shortest path in an Unweighted Bidirectional Graph
Given an unweighted bidirectional graph containing N nodes and M edges represented by an array arr[][2]. The task is to find the difference in length of the shortest and second shortest paths from node 1 to N. If the second shortest path does not exist, print 0. Note: The graph is connected, does not contain multiple edges and self loops. (2&lt;=N
15+ min read
Difference between BFS and Dijkstra's algorithms when looking for shortest path?
What is Dijkstra's Algorithm? Dijkstra's Algorithm is used for finding the shortest path between any two vertices of a graph. It uses a priority queue for finding the shortest path. For more detail about Dijkstra's Algorithm, you can refer to this article. What is BFS Algorithm? Breadth First Search (BFS) algorithm traverses a graph in a bread towa
2 min read
Shortest distance between two nodes in Graph by reducing weight of an edge by half
Given a weighted undirected graph consisting of N nodes and M edges, the task is to find the shortest distance between two nodes A and B by reducing the weight of one edge by half. Examples: Input: A = 0, B = 2, Below is the graph Output: 8Explanation:After reducing the weight of the edge connecting 1 and 2 by half modifies its new weight to 4. Now
11 min read
Time saved travelling in shortest route and shortest path through given city
Given a matrix mat[][] of size N * N, where mat[i][j] represents the time taken to reach from ith city to jth city. Also, given M queries in the form of three arrays S[], I[], and D[] representing source, intermediate, and destination respectively. The task is to find the time taken to go from S[i] to D[i] using I[i] city and the time that can be s
10 min read
Check if alternate path exists from U to V with smaller individual weight in a given Graph
Given a directed weighted graph with N vertices and M edges and an edge (U, V). The task is to find whether there is an alternate path present from U to V with individual weight of edges in alternate path less than the weight of direct path. If present print Yes else print No. Examples For the given directed graph: Input: N = 7, M = 10, U = 3, V =
10 min read
Path from a given source to a given destination having Kth largest weight in a Graph
Given a weighted graph consisting of N nodes and M edges, a source vertex, a destination vertex, and an integer K, the task is to find the path with Kth largest weight from source to destination in the graph. Examples: Input: N = 7, M = 8, source = 0, destination = 6, K = 3, Edges[][] = {{0, 1, 10}, {1, 2, 10}, {2, 3, 10}, {0, 3, 40}, {3, 4, 2}, {4
14 min read
Count number of paths whose weight is exactly X and has at-least one edge of weight M
Given an infinite tree and three numbers N, M, and X which has exactly N child from every node. Every edge has a weight of 1, 2, 3, 4..N. The task is to find the count of paths whose weight is exactly X and has a minimum of one edge of weight M in it. The diagram above shows a tree shown till level-3 and N = 3. Examples: Input: N = 3, M = 2, X = 3
8 min read
Maximize cost of segment having weight at most K from given weight and cost of N items
Given two arrays W[] and C[] containing weight and cost of N (1 to N) items respectively, and an integer K, find a segment from 1 to N, such that the total weight of the segment is at most K and the total cost is maximum. Print the cost of this segment. Examples: Input: N = 6, K = 20, W[] = {9, 7, 6, 5, 8, 4}, C[] = {7, 1, 3, 6, 8, 3}Output: 17Expl
12 min read
Choose maximum weight with given weight and value ratio
Given weights and values of n items and a value k. We need to choose a subset of these items in such a way that ratio of the sum of weight and sum of values of chosen items is K and sum of weight is maximum among all possible subset choices. Input : weight[] = [4, 8, 9] values[] = [2, 4, 6] K = 2 Output : 12 We can choose only first and second item
9 min read
Article Tags :
Practice Tags :
We use cookies to ensure you have the best browsing experience on our website. By using our site, you acknowledge that you have read and understood our Cookie Policy & Privacy Policy
Lightbox