¿Cómo funciona Breadth-First Search cuando se busca el camino más corto?

129

He investigado un poco y parece que me falta una pequeña parte de este algoritmo. Entiendo cómo funciona Breadth-First Search, pero no entiendo cómo exactamente me llevará a un camino específico, en lugar de solo decirme a dónde puede ir cada nodo individual. Creo que la forma más fácil de explicar mi confusión es proporcionar un ejemplo:

Entonces, por ejemplo, digamos que tengo un gráfico como este:

ingrese la descripción de la imagen aquí

Y mi objetivo es llegar de A a E (todos los bordes no están ponderados).

Comienzo en A, porque ese es mi origen. Pongo en cola A, seguido inmediatamente de la retirada de A y de explorarlo. Esto produce B y D, porque A está conectado a B y D. Por lo tanto, hago cola tanto B como D.

Detengo B y lo exploro, y descubro que conduce a A (ya explorado) y C, entonces hago cola C. Luego elimino D, y descubro que conduce a E, mi objetivo. Luego elimino C, y descubro que también conduce a E, mi objetivo.

Sé lógicamente que la ruta más rápida es A-> D-> E, pero no estoy seguro de cómo ayuda exactamente la búsqueda de amplitud, cómo debo registrar las rutas para que cuando termine, pueda analizar los resultados y ver Que el camino más corto es A-> D-> E?

Además, tenga en cuenta que en realidad no estoy usando un árbol, por lo que no hay nodos "primarios", solo hijos.

Jake
fuente
2
"Además, tenga en cuenta que en realidad no estoy usando un árbol, por lo que no hay nodos" principales ", solo secundarios", bueno, obviamente tendrá que almacenar el principal en algún lugar. Para DFS lo estás haciendo indirectamente a través de la pila de llamadas, para BFS tienes que hacerlo explícitamente. Nada que puedas hacer al respecto, me temo :)
Voo

Respuestas:

85

Técnicamente, Breadth-first search (BFS) por sí solo no le permite encontrar la ruta más corta, simplemente porque BFS no está buscando una ruta más corta: BFS describe una estrategia para buscar un gráfico, pero no dice que debe buscar nada en particular.

El algoritmo de Dijkstra adapta BFS para permitirle encontrar las rutas más cortas de una sola fuente.

Para recuperar la ruta más corta desde el origen a un nodo, debe mantener dos elementos para cada nodo en el gráfico: su distancia más corta actual y el nodo anterior en la ruta más corta. Inicialmente, todas las distancias se establecen en infinito, y todos los predecesores se configuran en vacío. En su ejemplo, establece la distancia de A en cero y luego continúa con el BFS. En cada paso, verifica si puede mejorar la distancia de un descendiente, es decir, la distancia desde el origen hasta el predecesor más la longitud del borde que está explorando es menor que la mejor distancia actual para el nodo en cuestión. Si puede mejorar la distancia, establezca la nueva ruta más corta y recuerde el predecesor a través del cual se ha adquirido esa ruta. Cuando la cola BFS está vacía, elija un nodo (en su ejemplo, es E) y recorra sus predecesores de regreso al origen.

Si esto suena un poco confuso, wikipedia tiene una buena sección de pseudocódigo sobre el tema.

dasblinkenlight
fuente
¡Gracias! Había leído el pseudocódigo anteriormente pero no pude entenderlo, su explicación hizo que hiciera clic para mí
Jake,
46
Me gustaría hacer la siguiente nota para las personas que vean esta publicación en el futuro: Si los bordes no están ponderados, no es necesario almacenar la "distancia más corta actual" para cada nodo. Todo lo que necesita ser almacenado es el padre para cada nodo descubierto. Por lo tanto, mientras examina un nodo y pone en cola a todos sus sucesores, simplemente configure el padre de esos nodos en el nodo que está examinando (esto se duplicará como marcarlos "descubiertos"). Si este puntero padre es NUL / nil / None para cualquier nodo dado, significa que BFS aún no lo ha descubierto o que es el nodo fuente / raíz en sí.
Shashank
@Shashank Si no mantenemos la distancia, ¿cómo podríamos saber la distancia más corta? Explique más.
Gaurav Sehgal
12
@gauravsehgal Ese comentario es para gráficos con bordes no ponderados. BFS encontrará la distancia más corta simplemente debido a su patrón de búsqueda radial que considera los nodos en orden de distancia desde el punto de partida.
Shashank
13
Un consejo para los lectores del comentario de @ Shashank: sin ponderar y con ponderación uniforme (por ejemplo, todos los bordes tienen un peso = 5) son equivalentes.
TWiStErRob
54

Como se señaló anteriormente, BFS solo se puede usar para encontrar la ruta más corta en un gráfico si:

  1. No hay bucles

  2. Todos los bordes tienen el mismo peso o no tienen peso.

Para encontrar el camino más corto, todo lo que tiene que hacer es comenzar desde la fuente y realizar una búsqueda amplia primero y detenerse cuando encuentre su nodo de destino. Lo único que necesita hacer es tener una matriz anterior [n] que almacenará el nodo anterior para cada nodo visitado. El anterior de fuente puede ser nulo.

Para imprimir la ruta, realice un ciclo simple a través de la matriz anterior [] desde el origen hasta llegar al destino e imprima los nodos. DFS también se puede utilizar para encontrar la ruta más corta en un gráfico en condiciones similares.

Sin embargo, si el gráfico es más complejo y contiene aristas y bucles ponderados, entonces necesitamos una versión más sofisticada de BFS, es decir, el algoritmo de Dijkstra.

javaProgrammer
fuente
1
Dijkstra si no hay pesas, use bellman ford algo si pesas
shaunak1111
¿BFS funciona para encontrar todas las rutas más cortas entre dos nodos?
Maria Ines Parnisari
35
@javaProgrammer, no está bien. BFS también se puede utilizar para encontrar la ruta más corta en un gráfico cíclico no ponderado. Si un gráfico no está ponderado, entonces se puede aplicar BFS para SP independientemente de tener bucles.
Andrei Kaigorodov
3
To print the path, simple loop through the previous[] array from source till you reach destination.Pero anterior de fuente es nulo. Creo que es lo que quería decir, backtrace from destination using the previous array until you reach the source.
aandis
2
¿Por qué dice que DFS funcionará en condiciones similares? ¿No es posible que DFS tome una ruta ingenua de ida y vuelta para llegar desde los nodos start-> end y, por lo tanto, le proporcione un camino que no sea el más corto?
James Wierzba
26

De tutorial aquí

"Tiene la propiedad extremadamente útil de que si todos los bordes de un gráfico no están ponderados (o tienen el mismo peso), la primera vez que se visita un nodo es la ruta más corta a ese nodo desde el nodo de origen"

acheron55
fuente
Esto es bueno para el nodo directamente accesible (1-> 2) (2 se alcanza directamente desde 1). Para el nodo no accesible directamente hay más trabajo (1-> 2-> 3, 3 no se alcanza directamente desde 1). Por supuesto, sigue siendo cierto considerando individualmente, es decir, 1-> 2 y 2-> 3 individualmente son caminos más cortos.
Manohar Reddy Poreddy
11

He perdido 3 días y
finalmente resolví una pregunta gráfica
utilizada para
encontrar la distancia más corta
usando BFS

Quiere compartir la experiencia.

When the (undirected for me) graph has
fixed distance (1, 6, etc.) for edges

#1
We can use BFS to find shortest path simply by traversing it
then, if required, multiply with fixed distance (1, 6, etc.)

#2
As noted above
with BFS
the very 1st time an adjacent node is reached, it is shortest path

#3
It does not matter what queue you use
   deque/queue(c++) or
   your own queue implementation (in c language)
   A circular queue is unnecessary

#4
Number of elements required for queue is N+1 at most, which I used
(dint check if N works)
here, N is V, number of vertices.

#5
Wikipedia BFS will work, and is sufficient.
    https://en.wikipedia.org/wiki/Breadth-first_search#Pseudocode

He perdido 3 días probando todas las alternativas anteriores, verificando y volviendo a verificar una y otra vez por encima de
que no son el problema.
(Intente pasar tiempo buscando otros problemas, si no encuentra problemas con los anteriores 5).


Más explicación del comentario a continuación:

      A
     /  \
  B       C
 /\       /\
D  E     F  G

Suponga que arriba el gráfico de su gráfico
va hacia abajo
Para A, los adyacentes son B y C
Para B, los adyacentes son D y E
Para C, los adyacentes son F y G

digamos, el nodo de inicio es A

  1. cuando llega a A, a, B y C, la distancia más corta a B y C desde A es 1

  2. cuando alcanza D o E, a través de B, la distancia más corta a A y D es 2 (A-> B-> D)

de manera similar, A-> E es 2 (A-> B-> E)

también, A-> F y A-> G es 2

Entonces, ahora en lugar de 1 distancia entre nodos, si es 6, entonces simplemente multiplique la respuesta por 6
ejemplos,
si la distancia entre cada uno es 1, entonces A-> E es 2 (A-> B-> E = 1 + 1 )
si la distancia entre cada uno es 6, entonces A-> E es 12 (A-> B-> E = 6 + 6)

sí, bfs puede tomar cualquier ruta
pero estamos calculando para todas las rutas

si tiene que ir de A a Z, entonces recorremos todos los caminos desde A hasta un I intermedio, y dado que habrá muchos caminos, descartamos todos menos el camino más corto hasta I, luego continuamos con el camino más corto hasta el siguiente nodo J
nuevamente si hay múltiples rutas de I a J, solo tomamos un
ejemplo más corto ,
supongamos,
A -> I tenemos distancia 5
(PASO) supongamos, I -> J tenemos múltiples rutas, de distancias 7 y 8, ya que 7 es más corto
tomamos A -> J como 5 (A-> I más corto) + 8 (más corto ahora) = 13,
entonces A-> J es ahora 13
, repetimos ahora arriba (PASO) para J -> K y así sucesivamente, hasta obtener a Z

Lea esta parte, 2 o 3 veces, y dibuje en papel, seguramente obtendrá lo que estoy diciendo, la mejor de las suertes


Manohar Reddy Poreddy
fuente
¿Podría por favor elaborar cómo logró encontrar el camino más corto con una primera búsqueda amplia. Una primera búsqueda amplia busca principalmente un nodo, puede haber n rutas a un nodo objetivo desde el nodo fuente y bfs puede tomar cualquier ruta. ¿Cómo estás determinando el mejor camino?
Perdedor
He agregado la parte de 'más explicación' a la respuesta anterior, avíseme si eso satisface
Manohar Reddy Poreddy
1
Veo que está intentando ejecutar un BFS en un gráfico ponderado. De las distancias 7 y 8, ¿por qué elegiste 8? ¿Por qué no 7? ¿Qué pasa si el nodo 8 no tiene más bordes al destino? El flujo tendrá que elegir 7 entonces.
Perdedor
buena pregunta, votada, sí, no estamos tirando, hacemos un seguimiento de todos los nodos adyacentes, hasta llegar a destino. BFS solo funcionará cuando solo haya distancias constantes como las 7 o las 8. Le di una genérica que tiene 7 y 8, que también se llama algoritmo de dijkstra.
Manohar Reddy Poreddy
lo siento, no estoy seguro de lo que quieres decir, ver en.wikipedia.org/wiki/Dijkstra's_algorithm
Manohar Reddy Poreddy
2

Según la respuesta de acheron55, publiqué una posible implementación aquí .
Aquí hay un breve resumen:

Todo lo que tiene que hacer es hacer un seguimiento de la ruta a través de la cual se ha alcanzado el objetivo. Una forma simple de hacerlo es empujar en Queuetoda la ruta utilizada para llegar a un nodo, en lugar del nodo en sí.
El beneficio de hacerlo es que cuando se alcanza el objetivo, la cola retiene el camino utilizado para alcanzarlo.
Esto también es aplicable a los gráficos cíclicos, donde un nodo puede tener más de un padre.

c0der
fuente
0

Visitando este hilo después de un período de inactividad, pero dado que no veo una respuesta completa, aquí están mis dos centavos.

La búsqueda de amplitud siempre encontrará la ruta más corta en un gráfico no ponderado. El gráfico puede ser cíclico o acíclico.

Vea a continuación el pseudocódigo. Este pseudocódigo asume que está utilizando una cola para implementar BFS. También supone que puede marcar vértices como visitados, y que cada vértice almacena un parámetro de distancia, que se inicializa al infinito.

mark all vertices as unvisited
set the distance value of all vertices to infinity
set the distance value of the start vertex to 0
push the start vertex on the queue
while(queue is not empty)   
    dequeue one vertex (well call it x) off of the queue
    if the value of x is the value of the end vertex: 
        return the distance value of x
    otherwise, if x is not marked as visited:
        mark it as visited
        for all of the unmarked children of x:
            set their distance values to be the distance of x + 1
            enqueue them to the queue
if here: there is no path connecting the vertices

Tenga en cuenta que este enfoque no funciona para gráficos ponderados; para eso, consulte el algoritmo de Dijkstra.

Matthew Russell
fuente
-6

La siguiente solución funciona para todos los casos de prueba.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

   public static void main(String[] args)
        {
            Scanner sc = new Scanner(System.in);

            int testCases = sc.nextInt();

            for (int i = 0; i < testCases; i++)
            {
                int totalNodes = sc.nextInt();
                int totalEdges = sc.nextInt();

                Map<Integer, List<Integer>> adjacencyList = new HashMap<Integer, List<Integer>>();

                for (int j = 0; j < totalEdges; j++)
                {
                    int src = sc.nextInt();
                    int dest = sc.nextInt();

                    if (adjacencyList.get(src) == null)
                    {
                        List<Integer> neighbours = new ArrayList<Integer>();
                        neighbours.add(dest);
                        adjacencyList.put(src, neighbours);
                    } else
                    {
                        List<Integer> neighbours = adjacencyList.get(src);
                        neighbours.add(dest);
                        adjacencyList.put(src, neighbours);
                    }


                    if (adjacencyList.get(dest) == null)
                    {
                        List<Integer> neighbours = new ArrayList<Integer>();
                        neighbours.add(src);
                        adjacencyList.put(dest, neighbours);
                    } else
                    {
                        List<Integer> neighbours = adjacencyList.get(dest);
                        neighbours.add(src);
                        adjacencyList.put(dest, neighbours);
                    }
                }

                int start = sc.nextInt();

                Queue<Integer> queue = new LinkedList<>();

                queue.add(start);

                int[] costs = new int[totalNodes + 1];

                Arrays.fill(costs, 0);

                costs[start] = 0;

                Map<String, Integer> visited = new HashMap<String, Integer>();

                while (!queue.isEmpty())
                {
                    int node = queue.remove();

                    if(visited.get(node +"") != null)
                    {
                        continue;
                    }

                    visited.put(node + "", 1);

                    int nodeCost = costs[node];

                    List<Integer> children = adjacencyList.get(node);

                    if (children != null)
                    {
                        for (Integer child : children)
                        {
                            int total = nodeCost + 6;
                            String key = child + "";

                            if (visited.get(key) == null)
                            {
                                queue.add(child);

                                if (costs[child] == 0)
                                {
                                    costs[child] = total;
                                } else if (costs[child] > total)
                                {
                                    costs[child] = total;
                                }
                            }
                        }
                    }
                }

                for (int k = 1; k <= totalNodes; k++)
                {
                    if (k == start)
                    {
                        continue;
                    }

                    System.out.print(costs[k] == 0 ? -1 : costs[k]);
                    System.out.print(" ");
                }
                System.out.println();
            }
        }
}
usuario3819236
fuente
44
Votado por no responder a la pregunta. Simplemente pegar un fragmento de código no funcionará en SO.
Rishabh Agrahari