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