La idea del algoritmo de Dijkstra es realmente fácil. Supongamos que arrojamos una gran colonia de hormigas en el nodo fuente u [math] u [/ math] en el momento 0 [math] 0 [/ math]. Se separaron de allí y siguen todos los caminos posibles a través del gráfico a una velocidad de una unidad por segundo. Entonces, la primera hormiga que encuentra el nodo objetivo v [matemáticas] v [/ matemáticas] lo hará en el momento d (u, v) [matemáticas] d (u, v) [/ matemáticas] segundos, donde d (u, v ) [math] d (u, v) [/ math] es la distancia más corta desde u [math] u [/ math] a v [math] v [/ math]. ¿Cómo encontramos cuando eso es? Solo necesitamos observar la expansión del frente de onda de las hormigas.
Con ese fin, mantengamos dos estructuras de datos:
- Un programa para realizar un seguimiento de los tiempos de llegada futuros de las primeras hormigas en ruta a cada nodo. (Se muestra en rojo en mi animación. Inicialmente, las hormigas solo están programadas para llegar a u [math] u [/ math] a la hora 0 [math] 0 [/ math]).
- Una matriz visitada para marcar los nodos que las hormigas ya han alcanzado, para asegurarse de que no desperdiciemos el seguimiento de todas las hormigas detrás de las líneas del frente. (Se muestra en verde en mi animación. Inicialmente, no se han visitado nodos).
Mientras observamos la marcha de las hormigas, actualizaremos estas estructuras de la siguiente manera. Considere la hora de llegada más temprana en el horario: nodo i [matemáticas] i [/ matemáticas] en el tiempo t [matemáticas] t [/ matemáticas]. En ese momento, haremos tres cosas:
- ¿Cuál es el pseudocódigo para encontrar la raíz (s) de [math] ax + bx ^ {0.5} + c = 0 [/ math]?
- Si el inicio se trata de resolver un problema, ¿qué problema están resolviendo las nuevas empresas de bebidas o cafés?
- ¿Cuál es la expresión regular para una fecha en el formato ’17 de marzo de 2016′?
- ¿Me puede mostrar cómo resolver este problema?
- ¿Qué es más eficiente para encontrar una solución para el problema del vendedor ambulante, una búsqueda puramente aleatoria o un algoritmo genético? ¿Hay un papel?
- Marcaremos el nodo i [math] i [/ math] como visitado.
- Eliminaremos i [math] i [/ math] del programa.
- Para cada borde desde i [matemática] i [/ matemática] a un nodo no visitado j [matemática] j [/ matemática], las hormigas van a comenzar a pulular por ese borde. (Las hormigas también comenzarán a pulular hacia los nodos visitados, pero no nos importan esas hormigas, ya que nunca serán las primeras en encontrar nuevos nodos). Notaremos en el cronograma que las hormigas llegarán a j [matemática] j [/ matemática] en el tiempo t + w [matemática] t + w [/ matemática], donde w [matemática] w [/ matemática] es la longitud del borde, a menos que el programa ya tuviera una entrada anterior para j [math] j [/ math], en cuyo caso no lo cambiaremos. Sin embargo, podríamos reemplazar una entrada posterior por j [math] j [/ math].
Luego, repetimos este proceso con la próxima hora de llegada más temprana en el programa, y así sucesivamente, hasta que las hormigas finalmente visiten el nodo v [matemáticas] v [/ matemáticas]. Dado que el calendario contendrá toda la información que necesitamos para determinar cuándo llegarán las hormigas, podemos implementar esto como un algoritmo en lugar de un horrible proyecto de feria de ciencias en la escuela intermedia.