Sí, pero con algunos ajustes al algoritmo.
El algoritmo de Dijkstra encuentra el camino más corto desde el punto inicial hasta el punto final. Para simplificar, digamos que el gráfico es una red de [matemática] M [/ matemática] por [matemática] N [/ matemática] nodos, con bordes ponderados no negativos entre nodos adyacentes, y el objetivo es encontrar el más corto ruta entre el punto [matemática] (0,0) [/ matemática] y [matemática] (M, N) [/ matemática] atravesando los bordes.
Permítanme citar primero el algoritmo de Dijkstra [1]
- Dado que muchos algoritmos de aprendizaje automático se ejecutan en GPU, ¿Julia sigue siendo una buena opción para eso?
- ¿Por qué Java utiliza diferentes algoritmos de clasificación para diferentes tipos de datos?
- Cómo encontrar si un número dado es primo o no
- ¿Las secuencias y series son importantes para el aprendizaje de algoritmos?
- Dados dos archivos de registro, cada uno con mil millones de nombres de usuario, ¿cómo podemos encontrar todos los nombres de usuario presentes en ambos archivos de registro de manera eficiente?
- Asigne a cada nodo un valor de distancia tentativo: ajústelo a cero para nuestro nodo inicial y al infinito para todos los demás nodos.
- Marque todos los nodos sin visitar. Establecer el nodo inicial como actual. Cree un conjunto de nodos no visitados llamado conjunto no visitado que consta de todos los nodos excepto el nodo inicial.
- Para el nodo actual, considere todos sus vecinos no visitados y calcule sus distancias tentativas . Por ejemplo, si el nodo actual A está marcado con una distancia tentativa de 6, y el borde que lo conecta con un vecino B tiene una longitud 2, entonces la distancia a B (a través de A) será 6 + 2 = 8. Si esta distancia es menor que la distancia tentativa previamente registrada de B, sobrescriba esa distancia. Aunque un vecino ha sido examinado, no está marcado como “visitado” en este momento, y permanece en el conjunto no visitado .
- Cuando hayamos terminado de considerar a todos los vecinos del nodo actual, marque el nodo actual como visitado y elimínelo del conjunto no visitado .
- Si el nodo de destino se ha marcado como visitado (cuando se planifica una ruta entre dos nodos específicos) o si la distancia tentativa más pequeña entre los nodos en el conjunto no visitado es infinito (cuando se planifica un recorrido completo), deténgase. El algoritmo ha terminado.
- Establezca el nodo no visitado marcado con la distancia tentativa más pequeña como el próximo “nodo actual” y vuelva al paso 3.
Supongamos que almacenamos el costo de la ruta más corta a cada nodo en una matriz [math] s [i] [j] [/ math]. Es decir, queremos encontrar el valor de [math] s [M] [N] [/ math]. En el algoritmo original de Dijkstra, este valor de la ruta más corta a cada punto [matemática] (i, j) [/ matemática] es independiente de la dirección de donde vino. Para imprimir la ruta más corta entre el punto inicial y el final, necesitamos almacenar la información sobre la dirección de donde vino.
Es decir, necesitamos agregar una nueva dimensión a la matriz [math] s [i] [j] [/ math], y convertirla en [math] s [i] [j] [k] [/ math]. En este caso, dado que cada nodo tiene 4 vecinos, [math] k [/ math] tiene 4 valores distintos, por ejemplo, [math] {0,1,2,3} [/ math]. Por lo tanto, almacenamos no solo el costo más bajo de llegar a ese nodo [matemática] (i, j) [/ matemática], sino también la dirección de donde vino. (Por ejemplo, k = 0 significa desde arriba, k = 1 significa desde la derecha, k = 2 significa desde la izquierda, k = 3 significa desde abajo). Es decir, en el paso 3, cuando encuentre la distancia tentativa a cada vecino, necesitaremos almacenarlo en la k adecuada para cada uno de sus vecinos.
Luego, cuando finaliza el algoritmo original de Dijkstra, es cuando recuperamos la información de la ruta. Tendremos que retroceder desde el punto [math] (M, N) [/ math] de forma recursiva, observando dónde está la dirección que dio el menor costo para llegar a ese nodo. Podemos hacer una primera búsqueda de amplitud o una primera búsqueda de profundidad para lograr esto. Una vez que presionamos [math] (0,0) [/ math] en la búsqueda, sabemos que tenemos una ruta que da la ruta más corta, y podemos imprimirla. Continuamos haciendo esto hasta que todos los caminos más cortos posibles hayan sido rastreados.
Hay algunos puntos a tener en cuenta al codificar este algoritmo:
- La comparación de costos en el paso 4 del algoritmo de Dijkstra es más complicada. En lugar de mirar [math] s [i] [j] [/ math] para nodos no visitados, necesitamos mirar el mínimo para todas las k en [math] s [i] [j] [k] [/ math ] en nodos no visitados.
- Si, al explorar los costos tentativos de llegar a los nodos adyacentes del nodo actual, encontramos otra manera de llegar a un nodo visitado en particular, con el mismo costo que el que ya tiene, entonces la matriz de costos [matemática] s [i] [j ] [k] [/ math] tiene que cambiarse para reflejar eso. Es decir, tenemos que hacer cambios en las direcciones donde podemos llegar a un nodo en particular, incluso si ya está visitado.
- Al final del algoritmo original de Dijkstra, se debe tener cuidado de no terminar antes de asegurarse de que no haya más rutas que produzcan el mismo costo que la ruta más corta al nodo [matemáticas] (M, N) [/ matemáticas]. Es decir, [matemática] s [i] [j] [k] [/ matemática] para todos los nodos no visitados debe ser mayor que el mínimo (para todas las k) para todos los nodos visitados.
Este algoritmo se puede generalizar fácilmente a un gráfico arbitrario. Supongamos que ahora hay nodos P en todo el gráfico. En este caso, podría ser más fácil hacer una matriz [math] s [p] [q] [/ math], donde p se refiere al nodo en el gráfico y q se refiere al nodo de donde proviene la ruta más corta, y p y q van de 0 a P-1. El algoritmo entonces procederá de manera similar a la descrita anteriormente.
[1] Algoritmo de Dijkstra
