Dado un gráfico donde cada borde tiene peso como 0 o 1. También se proporciona un vértice fuente en el gráfico. Encuentre la ruta más corta desde el vértice de origen hasta todos los demás vértices.
Ejemplo:
Input : Source Vertex = 0 and below graph
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
..................
En BFS normal de un gráfico, todos los bordes tienen el mismo peso, pero en 0-1 BFS algunos bordes pueden tener 0 peso y algunos pueden tener 1 peso. En esto, no usaremos la array bool para marcar los Nodes visitados, pero en cada paso verificaremos la condición de distancia óptima. Usamos una cola de dos extremos para almacenar el Node. Al realizar BFS, si se encuentra un borde que tiene un peso = 0, el Node se empuja al frente de la cola de dos extremos y si se encuentra un borde que tiene un peso = 1, se empuja al final de la cola de dos extremos.
El enfoque es similar a Dijkstra en el sentido de que si el Node anterior relaja la distancia más corta al Node, entonces solo se colocará en la cola.
La idea anterior funciona en todos los casos, cuando aparece un vértice (como Dijkstra), es el vértice de peso mínimo entre los vértices restantes. Si hay un vértice de peso 0 adyacente a él, entonces este adyacente tiene la misma distancia. Si hay un peso 1 adyacente, entonces este adyacente tiene la distancia máxima entre todos los vértices en la cola (porque todos los demás vértices son adyacentes al vértice reventado actualmente o adyacentes a los vértices reventados anteriormente).
A continuación se muestra la implementación de la idea anterior.
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
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>
Producción:
0 0 1 1 2 1 2 1 2
Este problema también puede ser resuelto por Dijkstra pero la complejidad temporal será O(E + V Log V) mientras que por BFS será O(V+E).
Referencia:
http://codeforces.com/blog/entry/22276
Este artículo es una contribución de Ayush Jha . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA