Dial’s Algorithm
We can also extend 0-1 BFS Algorithm for a graph having multiple weights until all the edge weights are less than W, where W is a small integer. We can maintain K buckets in the queue and start popping from the front of the queue. This way, we start moving from smaller weight buckets to larger weight buckets.
Example :
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
// Structure to represent an edge
struct Edge {
int to;
int weight;
};
// Function to add an edge to the graph
void addEdge(vector<vector<Edge> >& graph, int from, int to,
int weight)
{
graph[from].push_back({ to, weight });
}
// Function to perform 0-1 BFS algorithm
int zeroOneBFS(vector<vector<Edge> >& graph, int source,
int destination)
{
const int INF = 1e9;
vector<int> distance(graph.size(), INF);
deque<int> dq;
// Push source node to the queue with distance 0
dq.push_front(source);
distance[source] = 0;
// Loop until the queue is empty
while (!dq.empty()) {
int node = dq.front();
dq.pop_front();
// Traverse all adjacent nodes of the current node
for (const Edge& edge : graph[node]) {
int newDistance = distance[node] + edge.weight;
if (newDistance < distance[edge.to]) {
distance[edge.to] = newDistance;
// If the weight of the edge is 0
// push to the front of the queue
if (edge.weight == 0) {
dq.push_front(edge.to);
}
// If the weight of the edge is 1
// push to the back of the queue
else {
dq.push_back(edge.to);
}
}
}
}
// Return the distance to destination node
return distance[destination];
}
int main()
{
// Example usage
int vertices = 5;
vector<vector<Edge> > graph(vertices);
// Add edges to the graph
addEdge(graph, 0, 2, 0);
addEdge(graph, 0, 2, 1);
addEdge(graph, 1, 3, 0);
addEdge(graph, 2, 3, 1);
addEdge(graph, 3, 4, 0);
// Find the minimum number of edges to reverse from node
// 0 to node 4
int source = 0, destination = 4;
int minEdgesToReverse
= zeroOneBFS(graph, source, destination);
cout << minEdgesToReverse << endl;
return 0;
}
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
// Structure to represent an edge
class Edge {
int to;
int weight;
public Edge(int to, int weight)
{
this.to = to;
this.weight = weight;
}
}
public class Main {
// Function to add an edge to the graph
public static void addEdge(List<List<Edge> > graph,
int from, int to, int weight)
{
graph.get(from).add(new Edge(to, weight));
}
// Function to perform 0-1 BFS algorithm
public static int zeroOneBFS(List<List<Edge> > graph,
int source,
int destination)
{
final int INF = (int)1e9;
int[] distance = new int[graph.size()];
for (int i = 0; i < graph.size(); i++) {
distance[i] = INF;
}
Deque<Integer> dq = new ArrayDeque<>();
// Push source node to the queue with distance 0
dq.offerFirst(source);
distance[source] = 0;
// Loop until the queue is empty
while (!dq.isEmpty()) {
int node = dq.pollFirst();
// Traverse all adjacent nodes of the current
// node
for (Edge edge : graph.get(node)) {
int newDistance
= distance[node] + edge.weight;
if (newDistance < distance[edge.to]) {
distance[edge.to] = newDistance;
// If the weight of the edge is 0, push
// to the front of the queue
if (edge.weight == 0) {
dq.offerFirst(edge.to);
}
// If the weight of the edge is 1, push
// to the back of the queue
else {
dq.offerLast(edge.to);
}
}
}
}
// Return the distance to destination node
return distance[destination];
}
public static void main(String[] args)
{
int vertices = 5;
List<List<Edge> > graph = new ArrayList<>(vertices);
for (int i = 0; i < vertices; i++) {
graph.add(new ArrayList<>());
}
// Add edges to the graph
addEdge(graph, 0, 2, 0);
addEdge(graph, 0, 2, 1);
addEdge(graph, 1, 3, 0);
addEdge(graph, 2, 3, 1);
addEdge(graph, 3, 4, 0);
// Find the minimum number of edges to reverse from
// node 0 to node 4
int source = 0, destination = 4;
int minEdgesToReverse
= zeroOneBFS(graph, source, destination);
System.out.println(minEdgesToReverse);
}
}
from collections import deque
# Structure to represent an edge
class Edge:
def __init__(self, to, weight):
self.to = to
self.weight = weight
# Function to add an edge to the graph
def addEdge(graph, fromNode, to, weight):
graph[fromNode].append(Edge(to, weight))
# Function to perform 0-1 BFS algorithm
def zeroOneBFS(graph, source, destination):
INF = int(1e9)
distance = [INF] * len(graph)
dq = deque()
# Push source node to the queue with distance 0
dq.appendleft(source)
distance[source] = 0
# Loop until the queue is empty
while dq:
node = dq.pop()
# Traverse all adjacent nodes of the current node
for edge in graph[node]:
newDistance = distance[node] + edge.weight
if newDistance < distance[edge.to]:
distance[edge.to] = newDistance
# If the weight of the edge is 0, push to the front of the queue
if edge.weight == 0:
dq.appendleft(edge.to)
# If the weight of the edge is 1, push to the back of the queue
else:
dq.append(edge.to)
# Return the distance to destination node
return distance[destination]
# Example usage
vertices = 5
graph = [[] for _ in range(vertices)]
# Add edges to the graph
addEdge(graph, 0, 2, 0)
addEdge(graph, 0, 2, 1)
addEdge(graph, 1, 3, 0)
addEdge(graph, 2, 3, 1)
addEdge(graph, 3, 4, 0)
# Find the minimum number of edges to reverse from node 0 to node 4
source = 0
destination = 4
minEdgesToReverse = zeroOneBFS(graph, source, destination)
print(minEdgesToReverse)
# this code is contributed by Adarsh
// Define a class to represent an edge in the graph
class Edge {
constructor(to, weight) {
this.to = to; // Destination node of the edge
this.weight = weight; // Weight of the edge (0 or 1)
}
}
// Function to add an edge to the graph
function addEdge(graph, from, to, weight) {
graph[from].push(new Edge(to, weight)); // Add a new edge to the adjacency list of the 'from' node
}
// Function to perform the 0-1 BFS algorithm
function zeroOneBFS(graph, source, destination) {
const INF = 1e9; // Infinity value for representing unreachable distances
const distance = new Array(graph.length).fill(INF); // Array to store distances from the source node
const dq = []; // Deque (double-ended queue) for BFS traversal
dq.push(source); // Push the source node to the deque
distance[source] = 0; // Distance to the source node is 0
// Loop until the deque is empty
while (dq.length > 0) {
const node = dq.shift(); // Remove the first node from the deque
// Traverse all adjacent nodes of the current node
for (const edge of graph[node]) {
const newDistance = distance[node] + edge.weight; // Calculate the new distance to the adjacent node
// Update the distance if the new distance is shorter
if (newDistance < distance[edge.to]) {
distance[edge.to] = newDistance; // Update the distance to the adjacent node
// Push the adjacent node to the front or back of the deque based on the edge weight
if (edge.weight === 0) {
dq.unshift(edge.to); // Push to the front of the deque if the edge weight is 0
} else {
dq.push(edge.to); // Push to the back of the deque if the edge weight is 1
}
}
}
}
// Return the distance to the destination node
return distance[destination];
}
// Main function to execute the program
function main() {
const vertices = 5; // Total number of vertices in the graph
const graph = new Array(vertices).fill(null).map(() => []); // Initialize the adjacency list for the graph
// Add edges to the graph
addEdge(graph, 0, 2, 0);
addEdge(graph, 0, 2, 1);
addEdge(graph, 1, 3, 0);
addEdge(graph, 2, 3, 1);
addEdge(graph, 3, 4, 0);
// Find the minimum number of edges to reverse from node 0 to node 4
const source = 0, destination = 4; // Source and destination nodes for the BFS traversal
const minEdgesToReverse = zeroOneBFS(graph, source, destination); // Perform 0-1 BFS algorithm
console.log(minEdgesToReverse); // Output the result
}
// Call the main function to execute the program
main();
//This code is contributed by Prachi.
output :
1
0-1 BFS Algorithm for Competitive Programming
0-1 BFS Algorithm is a variation of simple BFS and is used to calculate Single vertex_source Shortest Path to all the nodes in a weighted graph provided the edges have weights 0 and 1 only. This algorithm runs in O(|E|) time which is much faster as compared to the Single Source Shortest Path Algorithms.