Encontrar todos los caminos más cortos entre dos nodos en gráfico no ponderado no dirigido
Necesito ayuda para encontrar todos los caminos más cortos entre dos nodos en un gráfico no ponderado no dirigido.
Soy capaz de encontrar uno de los caminos más cortos usando BFS, pero hasta ahora estoy perdido en cuanto a cómo podría encontrar e imprimir todos ellos.
¿Alguna idea del algoritmo / pseudocódigo que podría usar?
8 answers
Como advertencia, recuerde que puede haber exponencialmente muchos caminos más cortos entre dos nodos en un gráfico. Cualquier algoritmo para esto tomará potencialmente un tiempo exponencial.
Dicho esto, hay una modificación relativamente sencilla de BFS que puede usar como paso de preprocesamiento para acelerar la generación de todas las rutas posibles. Recuerde que a medida que BFS se ejecuta, procede hacia el exterior en "capas", obteniendo un único camino más corto a todos los nodos a distancia 0, luego distancia 1, luego distancia 2, sucesivamente. 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 distancia k desde el nodo de inicio. BFS descubre este nodo a distancia k + 1 encontrando algún camino de longitud k a un nodo a distancia k, luego extendiéndolo por algún borde.
Si su objetivo es encontrar todos los caminos más cortos, entonces puede modificar BFS extendiendo cada camino a un nodo a distancia k a todos los nodos a distancia k + 1 que conéctese a, en lugar de elegir un solo borde. Para hacer esto, modifique BFS de la siguiente manera: cada vez que procese un borde agregando su extremo en la cola de procesamiento, no marque inmediatamente ese nodo como hecho. En su lugar, inserte ese nodo en la cola anotada con la arista que 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 eliminas un nodo de la cola, lo marcas como se está haciendo y nunca lo inserte en la cola de nuevo. Del mismo modo, en lugar de almacenar un solo puntero principal, almacenará varios punteros principales, uno para cada nodo que se vinculó a 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 distancia k + 1 del nodo de inicio y tendrá un puntero a cada nodo de distancia k al que está conectado. A partir de ahí, se puede reconstruir todas las rutas más cortas desde algún nodo hasta el nodo de inicio listando todas las rutas posibles desde el nodo de su elección hasta el nodo de inicio dentro del DAG. Esto se puede hacer recursivamente:
- Solo hay una ruta desde el nodo de inicio hacia sí mismo, a saber, la ruta vacía.
- Para cualquier otro nodo, las rutas se pueden encontrar siguiendo cada borde saliente, luego extendiendo recursivamente esas rutas para obtener una ruta de regreso al nodo de inicio.
Espero que esto ayude!
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2013-01-03 19:15:04
@templatetypedef es correcto, pero se olvidó de mencionar la comprobación de distancia que debe hacerse antes de que se agreguen enlaces principales al nodo. Esto significa que se mantiene la distancia de la fuente en cada uno de los nodos e incrementa en uno la distancia para los hijos. 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 de la siguiente manera enlace.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2015-01-17 14:23:27
Me encontré con el problema similar mientras resolvía esto https://oj.leetcode.com/problems/word-ladder-ii /
La forma en que traté de tratar es primero encontrar la distancia más corta usando BFS, digamos que la distancia más corta es d. Ahora aplique DFS y en la llamada recursiva DFS no vaya más allá del nivel recursivo d.
Sin embargo, esto podría terminar explorando todas las rutas mencionadas por @templatetypedef.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2014-09-11 02:38:51
Primero, encuentre la distancia hasta el inicio de todos los nodos usando la búsqueda primero en anchura.
(si hay muchos nodos, puede usar un* y detenerse cuando la parte superior de la cola tenga distance-to-start > distance-to-start(end-node). Esto le dará todos los nodos que pertenecen a algún camino más corto)
Luego retrocede desde el nodo final. Cada vez que un nodo está conectado a dos (o más) nodos con una distancia menor al inicio, se ramifica en dos (o más) rutas.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2013-01-03 19:24:08
Templatetypedef su respuesta fue muy buena, muchas gracias por eso(!!), 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-Ees más largo que
A->B->C->E.Usted tendrá que tomar de seguimiento de las distancias de los padres que están añadiendo tan felizmente.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2013-09-02 16:41:51
Paso 1: Recorre el gráfico desde la fuente por BFS y asigna a cada nodo la distancia mínima desde la fuente
Paso 2: La distancia asignada al nodo de destino es la longitud más corta
Paso 3: Desde el origen, realice una búsqueda DFS a lo largo de todas las rutas donde la distancia mínima se incremente una por una hasta que se alcance el nodo de destino o se alcance la longitud más corta. Imprima la ruta cada vez que se alcance el nodo de destino.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2018-06-12 06:22:03
BFS se detiene cuando encuentras lo que quieres.
Hay que modificar el algoritmo para que continúe su ejecución cuando se encuentre la primera ruta. (elimine la instrucción return y guarde la ruta de alguna manera.
Puede finalizar la ejecución después de comprobar el último nodo del nivel que tiene los nodos finales de los caminos más cortos. (Todos los nodos finales de los caminos más cortos están en el mismo nivel)
También, hay algoritmo conocido que encuentran todos los más cortos caminos:
Algoritmo de Floyd-Warshall (tiene pseudocódigo)
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2013-01-03 17:57:16
Qué tal esto: lo encontré en Internet
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2013-01-21 08:50:51