¿Dijkstra en el camino más corto en múltiples grafos no ponderados?
Estoy tratando de averiguar cómo implementar el algoritmo de Djiktra para encontrar el camino más corto entre 2 gráficos no ponderados. La sugerencia que recibí fue usar 2 gráficos, uno para el color rojo y otro para el color azul. El costo siempre es 1 para viajar pero para acceder a un cuadro rojo mientras se está en azul, es necesario pagar 2 para cambiar de gráfico.
Principalmente estoy buscando sugerencias y referencias, ¿alguien ha hecho algo similar antes?
davy.ai
Para implementar el algoritmo de Dijkstra para encontrar el camino más corto entre dos grafos no ponderados con las restricciones dadas, podemos usar un enfoque modificado donde consideramos dos grafos: uno para el color rojo y otro para el color azul. Podemos asignar un costo de 1 para viajar entre nodos dentro del mismo grafo de color, pero para acceder a un nodo en el grafo de color opuesto, debemos pagar un costo de 2 para cambiar de grafo.
Para empezar, podemos mantener una matriz de distancias y una matriz de visitados para cada uno de los dos grafos. Podemos inicializar la matriz de distancias para ambos grafos de color con un valor grande (digamos, INF), excepto para el nodo fuente que tendrá una distancia de 0. También podemos inicializar la matriz de visitados con falso para todos los nodos.
A continuación, podemos usar una cola de prioridad para almacenar los nodos en orden de sus distancias crecientes. Podemos insertar el nodo fuente en la cola de prioridad para el grafo de color rojo con una distancia de 0. Luego, podemos iniciar el algoritmo de Dijkstra seleccionando el nodo con la distancia más baja de la cola de prioridad.
Para cada nodo seleccionado, podemos actualizar las distancias de sus vecinos en el mismo grafo de color usando la fórmula “distancia[u] + 1”. También podemos considerar los vecinos en el grafo de color opuesto y actualizar sus distancias usando la fórmula “distancia[u] + 2”. Si la distancia actualizada es menor que la distancia actual para un nodo, podemos actualizar la distancia y agregar el nodo a la cola de prioridad.
Podemos continuar con el proceso anterior hasta visitar el nodo de destino o hasta que la cola de prioridad quede vacía. Una vez que hayamos visitado el nodo de destino, podemos devolver la distancia a ese nodo desde ambos grafos de color y elegir el valor mínimo como el camino más corto.
Algunas referencias posibles para implementar este enfoque en C++ podrían ser: