¿Algoritmo de retroceso para resolver el camino más corto?

Question

He estado buscando ampliamente en toda la red anoche hasta hoy y parece que no puedo encontrar un recursos que discutan cómo resolver el problema de ruta más corto utilizando específicamente el algoritmo de retroceso. Intenté resolverlo con este algo, pero no tengo sentido para mí. Si es el problema de N-Queens, no sería tan complicado.

Entonces, ¿alguien puede dar algunos enlaces de Internet que me indiquen algunos recursos? Te lo agradezco mucho.

*ACTUALIZACIÓN: Solo curiosidad, ¿puede el algoritmo de retroceso realmente resolver el problema de ruta más corto?

Answer 1

Está cableado que se especificó para usar algoritm de retroceso, de hecho, Dijkstra SPFA o el algoritmo de Bellman-Ford serán perfecto para resolver su problema. Si tiene que usar el retroceso, me temo que solo puede alcanzar una complejidad de mal tiempo ---- Simplemente pruebe su próximo segmento de carretera y cuando la longitud de suma de sus segmentos elegidos excediera la "ruta más corta actual", comience a retroceder.

Answer 2

El retroceso puede resolverlo. Pero es muy lento ... Creo que necesitas dijkstra o (n^2), dijkstra con montón o (nlogn), bellman-ford o (ne) o spfa o (ke) (k≈22 ). Como para mí, prefiero spfa ...