algorithm - directed - ¿Cómo encontrar el número de caminos más cortos entre dos vértices, en gráfico dirigido y con tiempo lineal?

breadth first search vs depth first search

Question

Aquí está el ejercicio:

Sean v y w dos vértices en un grafo dirigido G = (V, E). Diseñe un algoritmo de tiempo lineal para encontrar el número de caminos más cortos (no necesariamente vértices disjuntos) entre v y w. Nota: los bordes en G no están ponderados

Para este impuesto especial, resumo de la siguiente manera:

1. Es un grafo dirigido
2. Solicita la cantidad de caminos más cortos diferentes . En primer lugar, las rutas deberían ser más cortas, luego podría haber más de una de esas rutas más cortas cuya longitud es la misma.
3. entre v y w, por lo que se deben contar tanto de v a w como de w a v.
4. tiempo lineal.
5. El gráfico no está ponderado.

De los puntos anteriores, tengo los siguientes pensamientos:

1. No necesito usar el Algoritmo de Dijkstra porque el gráfico no está ponderado y tratamos de encontrar todos los caminos más cortos, no solo uno solo.
2. Mantengo un count por el número de caminos más cortos
3. Me gustaría utilizar BFS de v primero y también mantener una información de global level
4. Aumento el global level por uno cada vez que BFS alcanza un nuevo nivel
5. También mantengo la información de shortest level corta para el camino más corto hacia w
6. La primera vez que me encuentro con W mientras viajo, asigno el global level shortest level y count++ ;
7. siempre que el global level igual al shortest level , aumento el count cada vez que me encuentro w de nuevo.
8. si el global level vuelve más grande que el shortest level , termino el viaje, porque estoy buscando el camino más corto, no el camino.
9. Luego hago 2 - 8 nuevamente para w a v

¿Mi algoritmo es correcto? Si hago v a w y luego w a v, ¿eso todavía se considera como tiempo lineal?

Answer 1

¿Puedo hacerlo de esta manera?

1. Atravieso usando BFS hasta que alcanzo el vértice de destino y mantengo los niveles
2. Una vez que alcanzo el nivel de destino, utilizo la tabla de niveles de la siguiente manera

Desde la tabla de niveles, empiezo a recorrer nuevamente el número de padres hasta el vértice en nuestro camino (la primera vez sería el vértice de destino).
En cada paso, multiplico el número de padres distintos encontrados en ese nivel particular por los caminos más cortos que puedo tener hasta el vértice de destino.
Subo los niveles, solo considerando los nodos que entran en mi camino y multiplico el número de padres distintos encontrados en cada nivel hasta que alcanzo el nivel 0.

¿Esto funciona?

Answer 2

Aquí hay algunas ideas sobre esto.

• Solo puede haber varias rutas más cortas desde v-> w hasta el nodo x, ya sea si hay varias rutas en x a través del mismo vertice o si x se encuentra varias veces en el mismo nivel DFS.

Prueba: si hay varias rutas que ingresan x través del mismo vértice, obviamente hay múltiples formas a través de x . Esto es simple. Ahora supongamos que hay una sola forma en x través de cada vértice yendo a x (como máximo).

Si x se ha encontrado antes, ninguna de las rutas actuales puede contribuir a otra ruta más corta. Como x se ha encontrado antes, todas las rutas que pueden seguir serán al menos una más largas que la ruta más corta anterior. Por lo tanto, ninguno de estos caminos puede contribuir a la suma.

Esto significa que, sin embargo, nos encontramos con cada nodo como máximo una vez y terminamos. Entonces, una BFS normal está bien.

• Ni siquiera necesitamos saber el nivel, en su lugar podemos obtener el número final una vez que nos encontramos con el nodo final.

Esto se puede compilar en un algoritmo muy simple, que es principalmente solo BFS.

 - Mark nodes as visited as usual with BFS.
 - Instead of adding just nodes to the queue in the DFS add nodes plus number of incoming paths.
 - If a node that has been visited should be added ignore it.
 - If you find a node again, which is currently in the queue, do not add it again, instead add the counts together.
 - Propagate the counts on the queue when adding new nodes.
 - when you encounter the final, the number that is stored with it, is the number of possible paths.

Answer 3

Como muestra qrqrq, su algoritmo falla en algunos gráficos, pero la idea de BFS es buena. En su lugar, mantenga una matriz z de tamaño |V| que inicializas a cero; mantenga el número de caminos más cortos hacia un vértice i descubierto a una distancia menor que el level en z[i] . También mantenga una matriz d de tamaño |V| tal que d[i] es la distancia de v al vértice i si esa distancia es menor que el level . Inicialice el level en 0, d[v] en 0 z[v] en 1 (hay una sola ruta de longitud 0 desde v hasta v ) y configure todas las otras entradas de d en -1 y de z en 0 .

Ahora, cada vez que encuentre una ventaja de i a j en su BFS, entonces:

• Si d[j] = -1 , entonces configure d[j] := level y z[j] := z[i] .
• Si d[j] = level , entonces configure z[j] := z[j] + z[i] .
• De lo contrario, no hagas nada.

La razón es que para cada ruta más corta de v a i , hay una ruta más corta de v a j . Esto dará la cantidad de caminos más cortos desde v hasta cada vértice en tiempo lineal. Ahora haz lo mismo otra vez, pero a partir de w .

Answer 4

Este algoritmo me parece correcto.

BFS, como saben, es una búsqueda de tiempo lineal ( O(N) ) porque el tiempo T requerido para completarlo es, en el peor, T = C + a * N , donde N es el número de nodos y C , a son cualquier constante fija

En su caso, realizar la búsqueda dos veces - primero de v a w , y luego de w a v - es (en el peor) 2T , o 2C + 2a * N , que también satisface el requisito de tiempo lineal O(N) si define un nuevo C'' = 2C , y un nuevo a'' = 2a , porque tanto C'' como a'' también son constantes fijas.

Answer 5

Tu algoritmo se rompe en un gráfico como

  *   *   *   1
 / / / / / / / /
v   *   *   *   w
 / / / / / / / /
  *   *   *   2

con todos los bordes dirigidos de izquierda a derecha. Cuenta dos caminos, uno a 1 y el otro a través de 2 , pero se puede llegar tanto a 1 como a 2 desde v por ocho caminos más cortos diferentes, para un total de dieciséis.

Answer 6

La solución más simple al cambiar BFS:

count (v) = 0, count (s) = 1. para cada vecino u de v, if (d (v) + 1 == d (u)), luego cuente (u) + = count (v). ahora restablece todo y haz lo mismo desde el vértice final.

Answer 7

int edgeCb( graphPT g, int x, int y )
{
    if ( dist[ y ] > dist[ x ] + 1 ) {
        dist[ y ] = dist[ x ] + 1; // New way
        ways[ y ] = ways[ x ]; // As many ways as it''s parent can be reached
    } else if ( dist[ y ] == dist[ x ] + 1 ) {
        ways[ y ] += ways[ x ]; // Another way
    } else {
        // We already found a way and that is the best
        assert( dist[ y ] < g->nv );
    }
    return 1;
}

El código anterior me está dando resultados adecuados para todo tipo de gráficos mencionados en esta publicación. Básicamente es una devolución de llamada de borde para el cruce de BFS.

dist [inicio] = 0; maneras [inicio] = 1;

para descansar todos los vértices dist [x] = numberOfVertices; // Esto está más allá del máximo posible de desaprobación

BFS (g, inicio);

Si los modos [end] no son cero, entonces eso representa el número de formas y dist [end] representa la distancia más corta.

Incase ways [end] == 0 significa que no se puede llegar al final desde el inicio.

Por favor, avíseme si hay algún agujero en este.