L'algorithme de Dijkstra permet de trouver le plus court chemin pour se rendre d'un noeud à un autre en connaissant le graphe. Dans la pratique, l'algorithme va retourner un tableau des parents en fonction d'un noeud i. En partant d'un point quelconque j, s'il existe un chemin jusqu'à i (c'est à dire si le noeud suivant, et donc le parent, est différent de -1), on obtient le chemin à suivre.
Soit n le nombre de noeuds et a le nombre d'arêtes. Complexité : Θ((a + n)log(n))
L'algorithme A* est une version améliorée de l'algorithme de Dijkstra. Au lieu d'explorer les noeuds par rapport à leur distance à la racine, il pondère la distance à la racine par rapport à la distance à un noeud ciblé. Cet algorithme va donc privilégier les chemins en direction de la cible.
Même complexité que l'algorithme de Dijkstra
Soit n le nombre de noeuds et a le nombre d'arêtes. Complexité : Θ((a + n)log(n))
On souhaite pouvoir se déplacer d'une case à une autre le plus rapidement possible. Pour ce faire, on utilise le tableau des parents retourné par les algorithmes précédants. En partant de la destination, on remonte dans les parents en empilant les cases dans un tableau jusqu'à atteindre notre point de départ. Si jamais il n'existe pas de chemin entre nos 2 points, on s'arrete. Une fois le chemin complet obtenu, il suffit juste de déplacer notre personnage.
L'algorithme de parcours en profondeur parcours les fils de la racine récursivement jusqu'à avoir tout exploré.
Soit n le nombre de noeuds et a le nombre d'arêtes. Complexité : Θ(a + n)