GPS - Algorithme Moore-Dijkstra

Exemple de Moore-Dijkstra

Présentation :

En théorie des graphes, cet algorithme va nous permettre de résoudre le problème du plus court chemin. En effet, ce dernier va permettre de calculer le chemin le plus court afin de se rendre d'un point A à un point B dans un graphe.

Remarque : L'algorithme s'applique à un graphe connexe dont le poids lié aux arêtes est une réel positif. Le but est de déterminer le plus court chemin entre eux point à l'aide d'un tableau.

Pseudo code de l'algorithme de Moore-Dijkstra :

Fonction Dijkstra (nœuds, fils, distance, début, fin)

Pour n parcourant nœuds

n.parcouru = infini // Peut être implémenté avec -1 (*)

n.précédent = 0

Fin pour

début.parcouru = 0

pasEncoreVu = nœuds

Tant que pasEncoreVu != liste vide

n1 = minimum(pasEncoreVu)

pasEncoreVu.enlever(n1)

Pour n2 parcourant fils(n1)

Si n2.parcouru > n1.parcouru + distance(n1, n2)

n2.parcouru = n1.parcouru + distance(n1, n2)

n2.précédent = n1

Fin si

Fin pour

Fin tant que

chemin = liste vide

n = fin

Tant que n != début

chemin.ajouterAvant(n)

n = n.précédent

Fin tant que

chemin.ajouterAvant(début)

Retourner chemin

Fin fonction Dijkstra