Algorithmes de chemin le plus court

Question

J'ai des questions sur un problème d'algorithme optimal sur un graphe pondéré. On me donne un edgelist avec des poids, une liste avec des points de sauvegarde, un noeud starte et un noeud final et la distance maximum pour un pas. La sortie doit être une liste de points de sauvegarde, accessibles en une seule étape depuis le noeud de départ et le noeud final.

J'ai pensé à une sorte d'algorithme de dijkstra à partir de chaque point de la liste des points de sauvegarde. Je ne sais pas si c'est une bonne idée, car si j'ai beaucoup de points de sauvegarde, je calcule plusieurs chemins plusieurs fois. Chaque idée/aide est la bienvenue!

Merci beaucoup d'avance!

Answer 1

Vous devez avoir la condition qu'un poids ne peut pas être négatif, sinon le problème devient très difficile à résoudre. Sinon, il s'agit juste d'une première recherche de largeur, avec la distance de chaque nœud visité. Donc, vous ne revisitez pas un nœud est un mouvement précédent l'a visité plus tôt à moindre coût.

Vous conservez une file d'attente prioritaire de tous les noeuds actifs, vous vérifiez donc le noeud le moins cher à chaque fois. La file d'attente prioritaire est en fait la partie la plus difficile à obtenir. Si vous vérifiez l'algorithme A * pour ma bibliothèque d'images binaires https://github.com/MalcolmMcLean/binaryimagelibrary vous pouvez prendre la file d'attente prioritaire pour là. Un * sur un labyrinthe est très similaire au plus court chemin sur un graphique, mais vous n'avez pas d'heuristique car vous devez avoir le chemin le plus court, et au lieu de 4/8 arêtes par tuile, vous avez des nœuds avec des nombres arbitraires de connexions .