Si todos los pesos de los bordes son positivos, puede aplicar el algoritmo de búsqueda A *:
Primero, use el algoritmo de Dijkstra para calcular la longitud de la ruta más corta desde cualquier otro nodo en el gráfico hasta el nodo de destino.
Luego, aplique el algoritmo A *. A partir de la ruta que consta solo del nodo de origen, mantiene una cola prioritaria que contiene todas las rutas no extendidas hasta ahora. Cada vez que ingrese la ruta en la cola de prioridad con el costo más bajo , extienda la ruta para tener un nodo más (puede haber múltiples nodos posibles) y coloque todas las rutas nuevas en la cola de prioridad. Sigue haciéndolo hasta que encuentre la ruta Kth al frente de la cola de prioridad que termina en el nodo de destino.
El costo es la suma de dos partes: una es la longitud de la ruta actual; la otra es la distancia desde el nodo final de la ruta al nodo de destino que ya ha encontrado con el algoritmo de Dijkstra.
Creo que también puede funcionar cuando hay pesos de borde negativos, siempre que no haya un ciclo de peso negativo (en ese caso, el camino más corto puede no existir). Todavía puede aplicar el algoritmo A *. Pero es posible que necesite usar otro algoritmo, por ejemplo, el algoritmo de Bellman-Ford, para calcular las distancias desde cualquier otro nodo al nodo de destino.
- ¿Por qué las funciones de límite superior e inferior en C ++ STL dan diferentes índices para el mismo número?
- ¿Cómo lidiar con la gestión eficiente de versiones y la compresión de múltiples versiones para bases de datos científicas?
- ¿Necesito aprender algoritmos y estructuras de datos en la interfaz?
- Con una base sólida en Python, ¿sería más importante aprender C o estructuras de datos y algoritmos primero?
- ¿Usar un tipo de inserción de 50 elementos tendrá el mismo tiempo de ejecución que usar un tipo de inserción de 10 elementos 5 veces?
