How to find 0-1 BFS for Shortest Path in a Binary Weight Graph

Here is problem statement :

Given a graph where each edge has a weight of either 0 or 1 and a source vertex, find the shortest path from the source vertex to every other vertex.

Code Level: Medium

Example:
Input: Source Vertex = 0, graph:
Output: Shortest distances from source: 0 0 1 1 2 1 2 1 2

The 0-1 BFS is similar to a normal BFS, but with the added condition that some edges have a weight of 0 and others have a weight of 1. Instead of using a bool array to mark visited nodes, at each step we check the optimal distance condition. A double ended queue is used to store the node and edges with weight 0 are pushed to the front, while edges with weight 1 are pushed to the back. This ensures that vertices are processed in increasing order of weight, similar to Dijkstra.

The code implementation uses a C++ program to find the shortest path from a source node to every other vertex in a binary graph. The program uses a vector to store edges and a double ended queue to perform BFS. The distances are initialized, with the source node having a distance of 0. The program continues to perform BFS until the queue is empty, checking the optimal distance condition at each step and pushing nodes with a weight of 0 to the front and weight of 1 to the back of the queue. Finally, the shortest distances are printed.

/**
 * Code Name: Python code to find 0-1 BFS for Shortest Path in a Binary Weight Graph
 * Code URI: https://devopsinvent.com/
 * Version: 1.0
 * Author: Devops Invent
 * Author URI: https://devopsinvent.com/
 * License: GNU General Public License v2 or later
 * License URI: http://www.gnu.org/licenses/gpl-2.0.html
 */

from collections import deque

# no. of vertices
V = 9

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

# function to add edges to the graph
def add_edge(u, v, wt):
    edges[u].append((v, wt))
    edges[v].append((u, wt))

# BFS function to find the shortest path from source vertex to every other vertex
def zero_one_BFS(src):
    # initialize distances from given source
    dist = [float('inf') for i in range(V)]
    dist[src] = 0

    # double ended queue to do BFS
    Q = deque()
    Q.append(src)

    while Q:
        v = Q.popleft()
        for to, weight in edges[v]:
            # checking for the optimal distance
            if dist[to] > dist[v] + weight:
                dist[to] = dist[v] + weight
                # Put 0 weight edges to front and 1 weight
                # edges to back so that vertices are processed
                # in increasing order of weights.
                if weight == 0:
                    Q.appendleft(to)
                else:
                    Q.append(to)

    # printing the shortest distances
    print(*dist)

# add edges to the graph
add_edge(0, 1, 0)
add_edge(0, 7, 1)
add_edge(1, 7, 1)
add_edge(1, 2, 1)
add_edge(2, 3, 0)
add_edge(2, 5, 0)
add_edge(2, 8, 1)
add_edge(3, 4, 1)
add_edge(3, 5, 1)
add_edge(4, 5, 1)
add_edge(5, 6, 1)
add_edge(6, 7, 1)
add_edge(7, 8, 1)

src = 0 # source node
zero_one_BFS(src)

Output:

0 0 1 1 2 1 2 1 2