L'algorithme de Dijkstra sans vecteur "précédent"

Question

Je suis intéressé par la recherche de la distance minimale entre n'importe quel nœud dans un graphique et la racine/source. Tous les liens ont un poids. Je ne pense pas que je devrais utiliser previous[], indiqué dans the Wikipedia article, puisque je n'ai pas besoin de connaître le parent de chaque nœud. Est-ce exact? De plus, si les poids sont tous égaux à un je suppose que je pourrais juste courir un BFS?

Answer 1

Il est tout à fait possible d'implémenter l'algorithme de Dijkstra sans pointeurs arrière; Je le sais parce que I've done it myself. :-) Le résultat est que vous ne serez pas en mesure de récupérer les chemins les plus courts une fois que vous avez terminé, mais si tout ce dont vous avez besoin sont les longueurs de chemin qui devrait être parfaitement bien. En ce qui concerne votre deuxième question, oui, vous pouvez simplement utiliser un BFS dans un direct avec des poids unitaires. L'algorithme de Dijkstra visite les nœuds dans l'ordre où ils seraient rencontrés dans un BFS si tous les bords ont le même coût positif.