Recherche du chemin le plus court entre les nœuds en utilisant Dijkstra et min heap C++

Question

Ceci est plus une question générale. J'ai une carte qui mappe le nom d'une ville à son nœud (contenant des informations de base telles que country, lat, long, etc.). Chaque nœud de ville a un tableau d'arêtes pointant vers des nœuds de destination. Le bord a un temps et un membre de coût. Je voudrais trouver le temps le plus court pour voyager entre deux nœuds, mais j'ai commencé à m'embrouiller sur la meilleure façon d'y arriver.

J'ai créé ma propre classe de segment de mémoire qui est basée sur un vecteur de nœuds de villes. Je suis en mesure de créer la carte ajouter les nœuds de la ville de la carte au tas min. J'ai écrit l'algorithme de dijkstra pour trouver le chemin le plus court et cela fonctionne pour certains chemins mais pas tous. Je crois c'est parce que quand je mets à jour le poids d'un nœud de ville pour l'algorithme de dijkstra, le tas n'est pas trié correctement. Une fois que je mets à jour le poids d'un nœud, comment suis-je censé ré-heapifier le tas pour que le poids le plus bas soit en haut?

Merci!

Answer 1

Si vous voulez trier tout le tas ont alors un rapide coup d'oeil à http://en.wikipedia.org/wiki/Heapsort

Il y a quelques pseudocode là-bas pour aider et vous pourriez avoir besoin de réorganiser pour obtenir le plus bas en haut, mais qui devrait fonctionner pour toi. Sinon, vous pouvez jeter un coup d'œil sur le bouillonnement du tas et l'appliquer à chaque étape plutôt que de réorganiser complètement le tas.

http://en.wikipedia.org/wiki/Binary_heap

Ils sont un peu complexe à décrire ici, mais bouillonnante tas haut/bas veillera à ce que votre tas est organisé correctement. Il est également intéressant de noter qu'un heaple fonctionnera à O (n log n) pour le pire des cas, alors que le bullage est O (log n) pour la plupart des opérations.