Dijkstra algorithme min-file d'attente de priorité
Je suis en train de mettre en œuvre l'algorithme de dijkstra avec file d'attente de priorité, mais je ne peux pas comprendre comment il fonctionne. J'ai lu beaucoup de guide sur le web mais je ne peux pas comprendre cet algorithme à tous.
Ma question: quelle est la priorité pour chaque nœud? Je pense que c'est le poids de l'entrée de bord avec un minimun de valeur, mais je ne suis pas sûr. Est-ce vrai?
Deuxième question, quand je l'extrait de la racine de la file d'attente, comment fonctionne si ce nœud n'est pas la contiguïté avec aucun des nœuds visités?
Si vous pensez que de Dijkstra est comme "en Largeur d'abord de recherche pour pondérée des graphiques," il devient assez facile à comprendre. Pour répondre à vos questions: 1. Pas tout à fait - c'est le minimum de la bords de traversée de loin. 2. Tout comme avec BFS, si ce n'est pas adjacent à un nœud visité, il ne peut pas être visité tout à fait encore. Si ce n'est pas accessible à partir d'un nœud visité, il ne sera jamais visité.
OriginalL'auteur giacomotb | 2013-08-19
Vous devez vous connecter pour publier un commentaire.
Vous devez utiliser
priority queue
où lavertex
avec la distance la plus courte à partir devertex
va avoir la plus haute priorité. Initialement, tous lesvertices
aura la plus courte distance de l'infini et de départvertex
aura la plus courte distance de 0.Commencer par l'insertion de tous les
vertices
(avec sesedges
) à partir du graphique à l'intérieur de laPQ
. Supprimervertex
de laPQ
et d'explorer toutes sesedges
. Comparer les distances les plus courtes, avec tous les adjacentevertices
et si la distance est inférieure à la distance la plus courte sur le courantvertex
, mise à jour adjacentesvertex
distance la plus courte à l'intérieur de laPQ
. Continuer toutPQ
n'est pas vide.Vertices
qui s'edges
pour se terminer par la plus courte distance de l'infini, car il n'est pas possible de "faire pour" depuis le départvertex
. Cependant, ils seront encore supprimés de laPQ
.Pseudocode
MIT OpenCourseWare Liens:
Chemin des problèmes de vue d'ensemble
Dijkstra
merci, fixe
OriginalL'auteur Patrik Fuhrmann