c++ - geeksforgeeks - Algoritmo Belman-Ford en 2d Array

floyd algorithm java

Question

Tengo un problema al aplicar un algoritmo Bellman-Ford a la matriz 2D (no al gráfico)

La matriz de entrada tiene m x n dimensiones:

           s[1,1] s[1,2] ... s[1,n] -> Exit
           s[2,1] s[2,2] ... s[2,n]
           ...
 Entry ->  s[m,1] s[m,2] ... s[m,n]

Y es similar a una habitación (cada entrada es una habitación con un costo de entrada s [x, y] ). Cada habitación podría tener un costo negativo , y debemos encontrar la ruta más barata desde la Entrada hasta la habitación elegida y hasta la Salida .

Por ejemplo, tenemos esta variedad de habitaciones y costos:

1   5   6
2  -3   4
5   2  -8

Y queremos caminar por la habitación [3,2] , s [3,2] = 4. Estamos comenzando la forma 5 en [1,3] y debemos caminar más [3,2] antes de ir a [3,3 ]

Y mi pregunta es, ¿cuál es la mejor manera de implementarlo en el algoritmo Bellman-Ford? Sé que el algoritmo Dijkstry no funcionará debido a un costo negativo.

¿Es para cada habitación de [0, maxHeight] y relajar a todos los vecinos? Me gusta esto:

   for (int i = height-1; i >= 0; --i) {
        for (int j = 0; j < width; ++j) {
            int x = i;
            int y = j;
            if (x > 0) // up
                Relax(x, y, x - 1, y);
            if (y + 1 < width) // right
                Relax(x, y, x, y + 1);
            if (y > 0) // left
                Relax(x, y, x, y - 1);
            if (x + 1 < height) // down
                Relax(x, y, x + 1, y);
        }
    }

¿Pero cómo puedo leer el costo de la habitación elegida y de la habitación a la salida?

Answer 1

Si sabe cómo moverse en el gráfico desde una matriz, puede desplazarse a un párrafo de condición adicional. Lea también el siguiente párrafo.

De hecho, puedes mirar ese edificio como en un gráfico.

Puedes ver como: (Olvidé puertas en segunda línea, lo siento).

Entonces, ¿cómo se puede implementar? Ignore por el momento una condición adicional (visite un vértice particular antes de irse).
Función de peso :
Deje que S[][] sea ​​una matriz de costo de entrada. Tenga en cuenta que sobre el peso del borde decide solo el vértice en el extremo. No tiene importancia si es (1, 2) -> (1,3) o (2,3) -> (1, 3) . El costo se define por el segundo vértice. para que la función se vea así:

cost_type cost(vertex v, vertex w) {
    return S[w.y][w.x];
}
//As you can see, first argument is unnecessary.

Bordes :
De hecho, no es necesario que mantenga todos los bordes en alguna matriz. Puede calcularlos en función cada vez que lo necesite. Los vecinos para el vértice (x, y) son (x+1, y) , (x-1, y) , (x, y+1) , (x, y-1) , si esos nodos existen. Tienes que verificarlo, pero es fácil. (Marque si new_x> 0 && new_x <max_x.) Puede verse así:

//Size of matrix is M x N
is_correct(vertex w) {
    if(w.y < 1 || w.y > M || w.x < 1 || w.x > N) {
        return INCORRECT;
    }
    return CORRECT;
}

Generar vecinos puede verse así:

std::tie(x, y) = std::make_tuple(v.x, v.y);
for(vertex w : {{x+1, y}, {x-1, y}, {x, y+1}, {x, y-1}}) {
    if(is_correct(w) == CORRECT) {//CORRECT may be true
        relax(v, w);
    }
}

Creo que no debería tomar memoria adicional para cuatro bordes. Si no conoce std::tie , mire cppreference. (Las variables adicionales x , y toman más memoria, pero creo que es más legible aquí. En su código puede que no aparezca).

Obviamente tienes que tener otra matriz 2D con distancia y (si es necesario) predecesor, pero creo que está claro y no tengo que describirlo.

Condición adicional :
Desea conocer el costo de ingresar para salir, pero tiene que visitar algún vértice compulsory . La manera más fácil de calcularlo es calcular el costo de enter a compulsory y de compulsory a exit . (Habrá dos cálculos separados.) No cambiará el gran O tiempo. Después de eso, puedes simplemente agregar resultados.

Solo tienes que garantizar que es imposible visitar la exit antes que compulsory . Es fácil, puede borrar los bordes salientes de la exit agregando una línea adicional en la función is_correct, (Entonces será necesario el vértice v ) o al generar el fragmento de código de los vecinos.

Ahora puedes implementarlo basándote en wikipedia . Tienes gráfico

¿Por qué no deberías escuchar?
Mejor manera es usar el algoritmo de Belman Ford desde otro vértice. Tenga en cuenta que si conoce el camino óptimo desde A hasta B, también conoce el camino óptimo desde B hasta A. ¿Por qué? Siempre tiene que pagar el último vértice y no paga primero, por lo que puede ignorar los costos de los mismos. El descanso es obvio.
Ahora, si sabes que quieres conocer las rutas A-> B y B-> C, puedes calcular B-> A y B-> C usando una sola vez BF del nodo B y la ruta inversa B-> A. Se acabó.
Solo tiene que borrar los bordes salientes de los nodos de entry y exit .

Sin embargo, si necesita un algoritmo muy rápido, debe optimizarlo. Pero es para otro tema, creo. Además, parece que nadie está interesado en la optimización dura.
Puedo agregar rápidamente, solo esas pequeñas y fáciles bases de optimización, que puedes ignorar la relajación de los correspondientes vértices lejanos. En conjunto, puede calcular la distancia de manera fácil, por lo que es una optimización agradable.
No mencioné la optimización conocida, porque creo que todos ellos están en un curso aleatorio de la web.