Imagine 2 personas comenzando dos puntos de partida diferentes en una matriz 2D. También tendrían puntos finales separados cuando atraviesan la matriz. Atravesar desde dos puntos tiene una dificultad correspondiente (peso). Usando el algoritmo de Djikstra, podemos determinar cuál sería la mejor ruta para que ambas personas lleguen a su destino. Dado que una persona solo puede moverse a un nodo a la vez y ambas personas se mueven simultáneamente, ¿cuál sería un buen algoritmo para determinar si chocarían entre sí a medida que atraviesan la matriz?
Cuando realiza dos búsquedas de Djikstra desde dos vértices iniciales, actualiza las matrices dist[] y prev[] (observando elpseudocódigo Wiki )
Agregue steps[] (para la distancia en número de bordes), y cuando modifique prev[v] ← u , también haga steps[v] = steps[u] + 1
Cuando lea la ruta más corta mediante iteraciones inversas, compare si los vértices de la intersección de dos rutas contienen el mismo valor en steps
Por ejemplo, encontró que los caminos se cruzan en los vértices 3 y 7. Pero A_steps[3] = 3, B_steps[3] = 2 , por lo que las personas caminan a través de esta celda en diferentes momentos. Y si A_steps[7] = 6, B_steps[7] = 6 significa que las personas se encuentran en este nodo en el sexto paso.