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