Lors de l'implémentation de l'algorithme de Dijkstra, vous utilisez une file d'attente prioritaire pour déterminer l'ordre dans lequel vous visitez nœuds.
La file d'attente de priorité contient tous les nœuds non visités, et vous permet de supprimer (puis de traiter) celle qui a la plus petite distance assignée. La file d'attente prioritaire est d'une importance critique, car elle garantit qu'un nœud n'est jamais visité jusqu'à ce que sa distance assignée soit précise et que le chemin le plus court connu soit effectivement le plus court. Cela signifie que vous n'aurez jamais à visiter et à traiter un nœud deux fois!
REMARQUE, cependant, l'algorithme de Dijkstra peut réduire la distance assignée d'un nœud plusieurs fois avant qu'il ne soit visité. Cela signifie que la file d'attente prioritaire doit prendre en charge dynamiquement la priorité croissante des nœuds. Les files d'attente de priorité standard fournies en Java et C++ ne supportent PAS cette opération et ne peuvent pas être utilisées dans l'algorithme de Dijkstra. A la place, vous devez implémenter vous-même votre file d'attente prioritaire en utilisant un tas dans une ArrayList ou un std :: vector.