algorithm - restricciones - Encontrar todos los caminos más cortos entre dos nodos en gráfico no dirigido no ponderado
redes algoritmo de dijkstra (8)
¿Qué tal esto? Lo encontré en Internet
Necesito ayuda para encontrar todas las rutas más cortas entre dos nodos en un gráfico no dirigido no ponderado .
Puedo encontrar uno de los caminos más cortos usando BFS, pero hasta ahora estoy perdido en cuanto a cómo podría encontrarlos e imprimirlos.
¿Alguna idea del algoritmo / pseudocódigo que podría usar?
@templatetypedef es correcto, pero olvidó mencionar acerca de la verificación de distancia que debe hacerse antes de que se agreguen enlaces principales al nodo. Esto significa que mantiene la distancia de la fuente en cada uno de los nodos e incrementa en uno la distancia para los niños. Debemos omitir este incremento y la adición de los padres en caso de que el niño ya haya sido visitado y tenga la distancia más baja.
public void addParent(Node n) {
// forbidding the parent it its level is equal to ours
if (n.level == level) {
return;
}
parents.add(n);
level = n.level + 1;
}
La implementación completa de Java se puede encontrar en el siguiente enlace.
BFS se detiene cuando encuentras lo que quieres.
Debe modificar el algoritmo para que continúe su ejecución cuando se encuentre la primera ruta. (elimine la declaración de return y guarde la ruta de alguna manera).
Puede finalizar la ejecución después de verificar el último nodo del nivel que tiene los nodos finales de las rutas más cortas. (Todos los nodos finales de las rutas más cortas están en el mismo nivel)
Además, existe un algoritmo conocido que encuentra todas las rutas más cortas:
Algoritmo de Floyd-Warshall (tiene pseudocódigo)
Como advertencia, recuerde que puede haber caminos exponencialmente más cortos entre dos nodos en un gráfico. Cualquier algoritmo para esto potencialmente tomará tiempo exponencial.
Dicho esto, hay una modificación relativamente directa de BFS que puede usar como paso de preprocesamiento para acelerar la generación de todas las rutas posibles. Recuerde que cuando BFS se ejecuta, avanza hacia afuera en "capas", obteniendo un camino más corto para todos los nodos a la distancia 0, luego distancia 1, luego distancia 2, etc. La idea motivadora detrás de BFS es que cualquier nodo a distancia k + 1 desde el nodo de inicio debe estar conectado por un borde a algún nodo a la distancia k desde el nodo de inicio. BFS descubre este nodo a la distancia k + 1 al encontrar una ruta de longitud k a un nodo a la distancia k, y luego lo extiende por un borde.
Si su objetivo es encontrar todas las rutas más cortas, entonces puede modificar BFS extendiendo cada ruta a un nodo a la distancia k a todos los nodos a la distancia k + 1 a la que se conectan, en lugar de elegir un solo borde. Para ello, modifique BFS de la siguiente manera: cada vez que procese un borde agregando su punto final en la cola de procesamiento, no marque inmediatamente ese nodo como hecho. En su lugar, inserte ese nodo en la cola anotado con qué borde siguió para llegar a él. Esto potencialmente le permitirá insertar el mismo nodo en la cola varias veces si hay varios nodos que se vinculan a él. Cuando elimina un nodo de la cola, lo marca como hecho y nunca lo inserta en la cola nuevamente. De manera similar, en lugar de almacenar un puntero padre único, almacenará varios punteros padres, uno para cada nodo que se vincule con ese nodo.
Si hace este BFS modificado, terminará con un DAG donde cada nodo será el nodo de inicio y no tendrá bordes salientes, o estará a la distancia k + 1 del nodo de inicio y tendrá un puntero a cada nodo de distancia k a la que está conectado. A partir de ahí, puede reconstruir todas las rutas más cortas desde un nodo al nodo de inicio al enumerar todas las rutas posibles desde su nodo de elección hasta el nodo de inicio dentro del DAG. Esto puede hacerse recursivamente:
- Solo hay una ruta desde el nodo de inicio a sí misma, es decir, la ruta vacía.
- Para cualquier otro nodo, las rutas se pueden encontrar siguiendo cada borde de salida, y luego extendiendo recursivamente esas rutas para generar un camino de regreso al nodo de inicio.
¡Espero que esto ayude!
En primer lugar, busque la distancia al inicio de todos los nodos utilizando la búsqueda de amplitud.
(si hay muchos nodos, puede usar A * y detenerse cuando la parte superior de la cola tiene distance-to-start > distance-to-start(end-node) . Esto le dará todos los nodos que pertenecen a los más cortos camino)
Luego solo retrocede desde el nodo final. Cada vez que un nodo está conectado a dos (o más) nodos con una menor distancia para comenzar, se bifurca en dos (o más) rutas.
Me encontré con el problema similar al resolver esto https://oj.leetcode.com/problems/word-ladder-ii/
La forma en que trato de lidiar es encontrar primero la distancia más corta usando BFS, digamos que la distancia más corta es d. Ahora aplique DFS y, en llamada recursiva DFS, no vaya más allá del nivel recursivo d.
Sin embargo, esto podría terminar explorando todas las rutas como se menciona en @templatetypedef.
Paso 1: recorra el gráfico desde la fuente por BFS y asigne a cada nodo la distancia mínima desde la fuente
Paso 2: la distancia asignada al nodo objetivo es la longitud más corta
Paso 3: desde la fuente, haga una búsqueda DFS a lo largo de todas las rutas donde la distancia mínima se incrementa de a una hasta que se alcance el nodo objetivo o se alcance la longitud más corta. Imprime la ruta siempre que se llegue al nodo objetivo.
templatetypedef su respuesta fue muy buena, muchas gracias por esa (!!), pero se perdió un punto:
Si tienes un gráfico como este:
A-B-C-E-F | | D------
Ahora imaginemos que quiero este camino:
A -> E.
Se expandirá así:
A-> B -> D-> C -> F -> E.
El problema es que tendrá F como padre de E, pero
A->B->D->F-E es más largo que
A->B->C->E. Tendrás que seguir el seguimiento de las distancias de los padres que tan felizmente estás agregando.