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

74
0

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/
*/

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
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
`0 0 1 1 2 1 2 1 2`