> Le Site du Zéro - Informatique

> Cours

> Tutoriels

> Programmation

> Algorithmique

> Le pathfinding avec Dijkstra

> Lecture du tutoriel

Le pathfinding avec Dijkstra

Par

Traize

Mise à jour : 06/01/2009

398 visites depuis 7 jours, classé 269/786

Bonjour !
Aujourd'hui nous allons étudier un algorithme assez connu (enfin, connu, c'est relatif bien sûr

) : l'algorithme de Dijkstra.
Cet algorithme sert à trouver le chemin le plus court d'un point à un autre. Pour vous c'est facile, mais votre ordinateur, lui, est bête et ne sait pas aller de chez vous à chez Mamie par le chemin le plus court (eh non... :euh:

).
Pour la suite, c'est par ici :pirate:

Retour en haut

Sommaire du tutoriel :

Qu'est-ce que le pathfinding ?
Histoire et principe de l'algorithme de Dijkstra
Application de l'algorithme à travers un exemple (non codé)
Limites et avantages de cet algorithme

Retour en haut

Qu'est-ce que le pathfinding ?

C'est l'histoire du livreur de pizzas, contraint de livrer ses commandes en moins d'une demi-heure avec pour seule arme un scooter faiblard et poussif. C'est aussi l'histoire de Monsieur Dupont qui, valise à la main, se rend à la gare de Strasbourg, direction Biarritz, sans bien savoir par où passer. C'est encore l'histoire du petit Epsien, synchronisant ses courses au Leclerc du coin avec le feu tricolore et qui cherche à épargner ses petits mollets. C'est enfin l'histoire d'Internet qui permet le transfert de tous types de données dans le monde entier via... quelle route, au fait ?

Le pathfinding est le fait de chercher à aller d'un point à un autre en trouvant le chemin le plus adapté (chemin le plus court, le plus rapide, uniquement sur autoroute, etc.).
Je vous invite à lire la définition du pathfinding sur Wikipédia qui est, je trouve, très complète.

J'ajoute que contrairement à l'algorithme A*, l'algorithme de Dijkstra est moins rapide et nécessite souvent plus de traitement, mais trouve le chemin le plus court.
Passons maintenant aux choses sérieuses :pirate:

Retour en haut

Histoire et principe de l'algorithme de Dijkstra

Histoire de l'algorithme et de son inventeur

L'algorithme de Dijkstra a été trouvé par M. Dijkstra (si, si, je vous jure

), Edsger de son prénom. Pour plus d'informations, vous pouvez consulter sa fiche sur Wikipédia, mais pour faire court, il a notamment trouvé cet algorithme du chemin le plus court, et a beaucoup participé au développement de langages tels l'ALGOL ou fait avancer les méthodes de programmation en se battant contre l'usage du GOTO en faveur d'une structure If - Then - Else à travers un article qu'il nomma "A case against the GOTO statement".

Principe de l'algorithme de Dijkstra

L'algorithme de Dijkstra se découpe en plusieurs parties.

Prérequis

Savoir ce qu'est un graphe et l'interpréter.
Ceci est un graphe de liaison représentant vaguement la France, nous l'utiliserons afin d'illustrer ce tutoriel .

Ce graphe est composé de 2 types d'objets : les noeuds, représentant des villes (ici dans des rectangles ou des ellipses), et les arêtes (les jointures entre différents noeuds), étant chacune affectée d'un poids (ici le nombre de kilomètres séparant chaque ville l'une de l'autre).
Chaque noeud doit avoir au minimum une liaison.

Le principe

Le principe de l'algorithme de Dijkstra est de trouver le chemin ayant le poids le plus faible entre 2 noeuds, sachant que le poids d'un chemin est la somme des poids des arêtes qui le composent.

Euh...

En clair, sur ce graphe, l'algorithme va trouver le chemin le plus court en distance (poids du chemin = sa longueur en km), sachant que la longueur du chemin est égale à la somme des longueurs de chaque arête le composant (poids d'une arête = sa longueur).
Compris ?

Compris ! Mais comment l'ordinateur va-t-il faire ?

La démarche algorithmique n'est pas évidente à trouver, même pour les humains. Pour l'appliquer il va nous falloir deux tableaux.

Un tableau à 3 lignes, que l'on va appeler "tableau des poids" contenant :
- dans la première ligne, la liste des noeuds (désignés soit par leur nom, soit plutôt par un numéro) ;
- dans la seconde ligne, un poids affecté à chaque noeud ;
- dans la troisième ligne, une variable vrai ou faux, qui servira à savoir si l'on est déjà passé par ce noeud.
Un autre tableau à une dimension, que l'on nommera "tableau des prédécesseurs" contenant ce que nous allons appeler les prédécesseurs de chaque noeud, c'est-à-dire le "noeud-père" qui précède le noeud dans le chemin que l'on prend pour y aller.
Exemple : si pour aller de Nantes à Strasbourg je suis ce trajet (cf. : graphe) : Strasbourg => Arras => Nantes, le prédécesseur de Nantes sera Arras, le prédécesseur de Arras sera Strasbourg, et Strasbourg lui, n'aura pas de prédécesseur (le pauvre... ).

Cela peut sembler un peu confus, mais accrochez-vous, je vais expliciter un peu.
Prenons un exemple, reprenant le graphe que je vous ai donné ci-dessus.
Supposons que l'on veuille aller de Brest à Montpellier, en prenant le chemin le plus court en distance.

Étapes de l'algorithme de Dijkstra

0) Tout d'abord on initialise les tableaux

Concernant le tableau des poids, on va mettre tous les poids à -1, montrant par là qu'aucun poids n'a encore été affecté à un noeud, et on va mettre toutes les variables oui ou non à non, car on n'est passé par aucun noeud (ce qui est logique vu que l'algorithme n'a pas encore commencé son travail

).
Ensuite, on met le poids du point de départ à 0 (bah oui, de Brest à Brest, il y a bien 0 km...

Tableau des poids
Nom du noeud	Poids	Déjà parcouru ?
Arras	-1	Non
Bordeaux	-1	Non
Brest	0	Non
Lyon	-1	Non
Marseille	-1	Non
Montpellier	-1	Non
Nantes	-1	Non
Paris	-1	Non
Poitiers	-1	Non
Strasbourg	-1	Non

Puis on met à 0 le tableau des antécédents.

Tableau des antécédents
Noeud	Antécédent du noeud
Arras	Aucun
Bordeaux	Aucun
Brest	Aucun
Lyon	Aucun
Marseille	Aucun
Montpellier	Aucun
Nantes	Aucun
Paris	Aucun
Poitiers	Aucun
Strasbourg	Aucun

1) On recherche le noeud non parcouru ayant le poids le plus faible et on indique donc qu'on l'a parcouru

La première fois, il s'agit forcément du noeud de départ. On met donc la variable oui ou non de Brest à oui.

2)On va rechercher ce que l'on appelle "les fils" du noeud où l'on se trouve

Si l'on découvre des fils au noeud, on va effectuer une condition sur chaque fils que l'on a trouvé :
Code : Autre

SI ( le noeud-fils n'a pas encore été parcouru )

ET QUE ( Poids(Noeud-père) + Poids(Liaison Noeud-père/Noeud-fils) < Poids(Noeud-fils) ) OU Poids(Noeud-fils) = -1 

{

    Poids(Noeud-fils) = Poids(Noeud-père) + Poids(Liaison Noeud-père/Noeud-fils)

    Antecedent(Noeud-fils) = Noeud-Père

}

Pourquoi on fait ça ? Et pourquoi on change les poids et les antécédents ? J'aimais bien les anciens, moi... :euh:

Décortiquons un peu ce code

.

Code : Autre

1
2
3

SI ( le noeud-fils n'a pas encore été parcouru )

ET QUE ( Poids(Noeud-père) + Poids(Liaison Noeud-père/Noeud-fils) < Poids(Noeud-fils) ) OU Poids(Noeud-fils) = -1

Que veux dire cette condition ?

Code : Autre

1	SI ( le noeud-fils n'a pas encore été parcouru )

Cette ligne vérifie que l'on n'a pas encore parcouru le noeud-fils (si, si, je vous jure

).
En effet, en réfléchissant un peu, si on a déjà parcouru le noeud-fils, c'est que la distance (Point de départ-Noeud fils) est inférieure à la distance (Point de départ-Noeud père) et que donc le Noeud-fils ne nous intéresse plus.

Code : Autre

1	Poids(Noeud-père) + Poids(Liaison Noeud-père/Noeud-fils) < Poids(Noeud-fils)

Poids(Noeud-père) est le poids pour aller jusqu'au Noeud-père. Ici cela représente la distance parcourue du noeud de départ jusqu'au noeud où l'on se trouve ;
Poids(Liaison Noeud-père/Noeud-fils) représente ici la distance entre le Noeud-père où l'on se trouve, et le Noeud-fils ;
Poids(Noeud-fils) représente la distance à parcourir pour aller du noeud de départ au Noeud-fils.

Concrètement, cela veut dire que la distance pour aller du départ au Noeud-fils, en passant par le Noeud-père où l'on se trouve, est plus petite que la distance pour aller du départ au Noeud-fils que l'on avait déjà trouvée en passant par un autre chemin.

Si on se trouve dans ce cas précis alors notre condition est validée, on exécute ce code :

Code : Autre

1
2
3

Poids(Noeud-fils) = Poids(Noeud-père) + Poids(Liaison Noeud-père/Noeud-fils)

Antecedent(Noeud-fils) = Noeud-Père

On change donc le poids du Noeud-fils, en mettant celui du chemin passant par le Noeud-père, et on indique dans le tableau d'antécédents, que l'étape précédente du Noeud-fils est le Noeud-père.

3) On boucle en retournant à l'étape 1) tant que...

Tant que le noeud ayant le poids le plus faible n'est pas le noeud d'arrivée.
En effet, quand le noeud ayant le poids le plus faible sera le noeud d'arrivée, cela voudra dire que l'on a trouvé le chemin le plus court pour y aller en partant du noeud de départ.

Le tour est joué :magicien:

Oui mais... comment je retrouve ce chemin ??

C'est là que le tableau des antécédents est utile !
On va prendre l'antécédent du noeud d'arrivée (dans notre exemple, Montpellier), puis l'antécédent de l'antécédent de Montpellier, puis l'antécédent de l'antécédent de l'antécédent de Montpellier puis l'antécédent de l'antécédent de...
Enfin bref, vous avez compris

.
Exemple : supposons qu'à la fin de l'exécution de l'algorithme, vous avez un tableau d'antécédents qui ressemble à ça, et que vous cherchiez à aller de Nantes à Lyon.

Noeud	Antécédent du noeud
Arras	Nantes
Bordeaux	Nantes
Brest	Nantes
Lyon	Paris
Marseille	Aucun
Montpellier	Poitiers
Nantes	Aucun
Paris	Nantes
Poitiers	Bordeaux
Strasbourg	Arras

Vous allez regarder l'antécédent de Lyon : Paris, l'antécédent de Paris : Nantes, hop ! Vous êtes arrivés à Nantes en marche arrière !! (OK, je sors...)
Vous remettez le tout dans l'ordre, et vous avez votre chemin le plus court :

Nantes => Paris => Lyon

Évidemment, en regardant le graphe, cela semble évident et inutile d'utiliser un algorithme pour arriver à un résultat si trivial, mais imaginez un peu que vous modélisiez toutes les villes et toutes les routes de la France ? Ah ! ça devient intéressant là, non

?
Imaginez qu'en plus de ça, vous ajoutiez toutes les rues de chaque ville :diable:

, ça deviendrait carrément indispensable...

Retour en haut

Application de l'algorithme à travers un exemple (non codé)

Vous avez tout compris ?

Euh oui, mais c'est peut-être encore un peu confus pour moi...

J'imagine

, c'est pour ça que nous allons voir un exemple concret pas à pas. Ne vous inquiétez pas, par souci d'ouverture, c'est un exemple n'utilisant aucun langage, que ce soit le C, le PHP, etc. (je suis gentil, hein ? :-°

).

Reprenons le graphe de tout à l'heure.

Supposons que nous soyons à Bordeaux et que nous voulions aller à Strasbourg.

On initialise les tableaux

Tableau des poids
Nom du noeud	Poids	Déjà parcouru ?
Arras	-1	Non
Bordeaux	0	Non
Brest	-1	Non
Lyon	-1	Non
Marseille	-1	Non
Montpellier	-1	Non
Nantes	-1	Non
Paris	-1	Non
Poitiers	-1	Non
Strasbourg	-1	Non

Tableau des antécédents
Noeud	Antécédent du noeud
Arras	Aucun
Bordeaux	Aucun
Brest	Aucun
Lyon	Aucun
Marseille	Aucun
Montpellier	Aucun
Nantes	Aucun
Paris	Aucun
Poitiers	Aucun
Strasbourg	Aucun

On recherche le noeud avec le plus petit poids

Il s'agit de Bordeaux.

On liste les fils de Bordeaux

Nantes :
- est-on déjà passé par Nantes ?
  => Non ;
- kilométrage de Nantes > kilométrage de Bordeaux + distance Bordeaux-Nantes ?
  OU
  kilométrage de Nantes non défini (= -1) ?
  => Oui :
  - kilométrage de Nantes = kilométrage de Bordeaux + distance Bordeaux-Nantes ;
  - kilométrage de Nantes = 0 + 334 = 334 ;
  - antécédent de Nantes = Bordeaux.
Poitiers :
- est-on déjà passé par Poitiers ?
  => Non ;
- kilométrage de Poitiers > kilométrage de Bordeaux + distance Bordeaux-Poitiers ?
  OU
  kilométrage de Poitiers non défini (= -1) ?
  => Oui :
  - kilométrage de Poitiers = kilométrage de Bordeaux + distance Bordeaux-Poitiers ;
  - kilométrage de Poitiers = 0 + 237 = 237 ;
  - antécédent de Poitiers = Bordeaux.

Aperçu des tableaux

Tableau des poids
Nom du noeud	Poids	Déjà parcouru ?
Arras	-1	Non
Bordeaux	0	Oui
Brest	-1	Non
Lyon	-1	Non
Marseille	-1	Non
Montpellier	-1	Non
Nantes	334	Non
Paris	-1	Non
Poitiers	237	Non
Strasbourg	-1	Non

Tableau des antécédents
Noeud	Antécédent du noeud
Arras	Aucun
Bordeaux	Aucun
Brest	Aucun
Lyon	Aucun
Marseille	Aucun
Montpellier	Aucun
Nantes	Bordeaux
Paris	Aucun
Poitiers	Bordeaux
Strasbourg	Aucun

Et on recommence ! On recherche le noeud non entouré avec le poids le plus faible

Il s'agit de Poitiers.

On liste ses fils

Bordeaux :
- est-on déjà passé par Bordeaux ?
  => Oui.
Montpellier :
- est-on déjà passé par Montpellier ?
  => Non ;
- kilométrage de Montpellier > kilométrage de Poitiers + distance Poitiers-Montpellier ?
  OU
  kilométrage de Montpellier non défini (= -1) ?
  => Oui :
  - kilométrage de Montpellier = kilométrage de Poitiers + distance Poitiers-Montpellier ;
  - kilométrage de Montpellier = 237 + 557 = 794 ;
  - antécédent de Montpellier = Poitiers.
Paris :
- est-on déjà passé par Paris ?
  => Non ;
- kilométrage de Paris > kilométrage de Poitiers + distance Poitiers-Paris ?
  OU
  kilométrage de Paris non défini (= -1) ?
  => Oui :
  - kilométrage de Paris = kilométrage de Poitiers + distance Poitiers-Paris ;
  - kilométrage de Paris = 237 + 338 = 575 ;
  - antécédent de Paris = Poitiers.

Aperçu des tableaux

Tableau des poids
Nom du noeud	Poids	Déjà parcouru ?
Arras	-1	Non
Bordeaux	0	Oui
Brest	-1	Non
Lyon	-1	Non
Marseille	-1	Non
Montpellier	794	Non
Nantes	334	Non
Paris	575	Non
Poitiers	237	Oui
Strasbourg	-1	Non

Tableau des antécédents
Noeud	Antécédent du noeud
Arras	Aucun
Bordeaux	Aucun
Brest	Aucun
Lyon	Aucun
Marseille	Aucun
Montpellier	Poitiers
Nantes	Bordeaux
Paris	Poitiers
Poitiers	Bordeaux
Strasbourg	Aucun

Et on recommence ! On recherche le noeud non entouré avec le poids le plus faible

Il s'agit de Nantes.

On liste ses fils

Arras :
- est-on déjà passé par Arras ?
  => Non ;
- kilométrage de Arras > kilométrage de Nantes + distance Nantes-Arras ?
  OU
  kilométrage de Arras non défini (= -1) ?
  => Oui :
  - kilométrage de Arras = kilométrage de Nantes + distance Nantes-Arras
  - kilométrage de Arras = 334 + 561 = 895 ;
  - antécédent de Arras = Nantes.
Bordeaux :
- est-on déjà passé par Bordeaux ?
  => Oui.
Brest :
- est-on déjà passé par Brest ?
  => Non ;
- kilométrage de Brest > kilométrage de Nantes + distance Nantes-Brest ?
  OU
  kilométrage de Brest non défini (= -1) ?
  => Oui :
  - kilométrage de Brest = kilométrage de Nantes + distance Nantes-Brest ;
  - kilométrage de Brest = 334 + 298 = 632 ;
  - antécédent de Brest = Nantes.
Paris :
- est-on déjà passé par Paris ?
  => Non ;
- kilométrage de Paris > kilométrage de Nantes + distance Nantes-Paris ?
  OU
  kilométrage de Paris non défini (= -1) ?
  => Non.
  - Remarque : donc on n'y touche pas.

Aperçu des tableaux

Tableau des poids
Nom du noeud	Poids	Déjà parcouru ?
Arras	895	Non
Bordeaux	0	Oui
Brest	632	Non
Lyon	-1	Non
Marseille	-1	Non
Montpellier	794	Non
Nantes	334	Oui
Paris	575	Non
Poitiers	237	Oui
Strasbourg	-1	Non

Tableau des antécédents
Noeud	Antécédent du noeud
Arras	Nantes
Bordeaux	Aucun
Brest	Nantes
Lyon	Aucun
Marseille	Aucun
Montpellier	Poitiers
Nantes	Bordeaux
Paris	Poitiers
Poitiers	Bordeaux
Strasbourg	Aucun

Je ne continue pas afin d'épargner à ce tutoriel un alourdissement énorme et d'éviter qu'il ne fasse cinq kilomètres de long (et aussi parce que c'est assez long à mettre en forme pour moi

).
Toutes les différentes situations conditionnelles concernant les noeuds-fils ont été rencontrées, et il suffit de continuer en boucle, jusqu'à ce que le noeud de poids le plus faible soit le noeud d'arrivée (Strasbourg).

Je vous invite à finir de trouver le chemin, et je vous laisse les états des tableaux des poids et des antécédents quand on est arrivé à Strasbourg, comparez-les avec les vôtres

.

Secret (cliquez pour afficher)

Tableau des antécédents
Noeud	Antécédents du noeud
Arras	Paris
Bordeaux	Aucun
Brest	Nantes
Lyon	Paris
Marseille	Montpellier
Montpellier	Poitiers
Nantes	Bordeaux
Paris	Poitiers
Poitiers	Bordeaux
Strasbourg	Arras

Tableau des poids
Nom du noeud	Poids	Déjà parcouru ?
Arras	760	Oui
Bordeaux	0	Oui
Brest	632	Oui
Lyon	1040	Oui
Marseille	965	Oui
Montpellier	794	Oui
Nantes	334	Oui
Paris	575	Oui
Poitiers	237	Oui
Strasbourg	1282	Oui

Dans cet exemple, on est passé par toutes les villes mais ce n'est pas toujours le cas.
Exemple : aller d'Arras à Brest.

Chemin le plus court (roulement de tambours...

) :
1282 kilomètres parcourus !
Pour un total de

Bordeaux -> Poitiers -> Paris -> Arras -> Strasbourg

Retour en haut

Limites et avantages de cet algorithme

L'algorithme de Dijkstra, très puissant, admet quand même quelques limites :

il demande une certaine masse de traitements quand le graphe devient grand. Par exemple, comme l'explique Haveo dans son tutoriel "Le pathfinding avec A*", quand la puissance matérielle est limitée, où que l'on souhaite traiter rapidement le problème du chemin le plus court, on peut utiliser d'autres algorithmes, tel A*, qui sont certes moins précis parfois, mais qui sont plus rapides et moins gourmands en ressources ;
on ne peut pas affecter aux liaisons un poids négatif, sinon l'algorithme est faussé et retournera des résultats faux.

Cependant il a plusieurs avantages :

contrairement à l'algorithme A* par exemple, il trouve toujours le chemin ayant le poids le plus faible ;
il n'est pas si dur à comprendre et à mettre en place (surtout avec quelqu'un qui explique aussi bien que moi ) ;
il peut être utilisé pour d'autres applications que la distance la plus courte d'un point à un autre.
On peut remplacer les villes par d'autres choses. J'avais par exemple fait un graphe où les liaisons étaient des pertes d'argent et les noeuds étaient des choix économiques d'entreprise.

Retour en haut

Voilà, c'est fini !
J'espère avoir éclairé votre lanterne sur le fonctionnement de Mappy

.
À noter cependant que ma manière d'implémenter peut probablement être améliorée. J'utilise pour ma part une boucle qui se répète jusqu'au noeud d'arrivée, on peut utiliser à la place une approche récursive, chacun ses goûts.

J'ai implémenté cet algorithme en langage C dans un de mes projets scolaires : si cela intéresse quelqu'un, je peux probablement extraire le module du chemin le plus court et partager les sources. Contactez-moi par message privé

Retour en haut

Retour en haut

56 commentaires pour "Le pathfinding avec Dijkstra"

Note moyenne : 3.67 / 4 (21 votes)

Pseudo

Commentaire

tit_toinou

# Posté le 09/03/2011 à 20:32:46

J'ai pas encore tout compris, mais ce que j'ai pigé m'a permis de résoudre l'exercice 83 du projet d'Euler

.
Donc merci pour ce tutoriel !

Tu pourrais mettre des liens pour les problèmes 67 , 81 , 82 , 83 d'ailleurs

(même si les trois premiers c'est vrai qu'on peut faire mieux sans).

[Cod'Art][Processing] Visualisation des fonctions complexes

jQuery : écrivez moins pour faire plus !

Megaz

# Posté le 07/06/2011 à 01:38:30

Avis : Très bon

Ville : Bruxelles
Pays : Belgique

Bonjour !

Infini

Tout d'abord un petit commentaire peu important, pourquoi ne pas utiliser "infini" à la place de "-1" ? Ainsi la condition est seulement "Si Poids + Distance < poids" et non "Poids + Distance < poids OU poids = -1" etc.
Let's do $\infty$

Liste ouverte

Cela fait un moment que l'on trouve qu'il serait intéressant de parler d'une file de priorité pour ne pas devoir trouver le minimum en $O(n)$ où n est la taille de la "liste ouverte".
En l'occurence ici une ville appartient à la liste ouverte si elle n'a pas encore été visitée et que son Poids est différent de -1 (Non visitée ET $Poids \neq -1$ )
Et les discussions à ce propos sont parfois assez floues dans les commentaires pour un débutant. Elles partent dans tout les sens, et je rappelle que l'enjeu est d'avoir une structure qui fait rapidement ces 3 opérations : (Les commentaires oublient souvent la 2ème !!)

Insertion
Changer un Poids
Enlever le minimum

Cette liste pourrait être simplement un tas placé à côté des tableaux.
Je trouve que le tas est une structure de donnée assez simple pour être introduite ici.

Insertion : $O(log(n))$
Changer un Poids : $O(log(n))$
Enlever le minimum : $O(log(n))$

Ainsi, par exemple à la dernière étape donnée on aurait :

Noeud	Poids	Visité	Antécédent	N°
Arras	895	Non	Nantes	2
Bordeaux	0	Oui	Aucun	-
Brest	632	Non	Nantes	1
Lyon	-1	Non	Aucun	-
Marseille	-1	Non	Aucun	-
Montpellier	794	Non	Poitiers	3
Nantes	334	Oui	Bordeaux	-
Paris	575	Non	Poitiers	0
Poitiers	237	Oui	Bordeaux	-
Strasbourg	-1	Non	Aucun	-

Et le tas serait :

Tas - File de priorité - Liste ouverte
Paris (575)
Brest (632)		Arras (895)
Montpellier (794)	Aucune	Aucune	Aucune

Et donc la prochaine ville est Paris.

Le numéro dans le tableau en haut correspond au numéro du tas si celui-ci est stocké sous-forme de tableau.

Ainsi quand on ajoute une ville : on lui met le numéro "taille", on augmente la taille, et on le "remonte" en faisant des échanges tant que la règle du tas-min n'est pas respectée. Un échange se ferait sur le N° dans le tas dans le premier tableau, et la place dans le tas sur celui-ci.
Pour la modification d'un poids, même chose, on modifie son poids et on le remonte tant que la règle n'est pas respectée (Ou on le descend si le poids a été augmenté, mais dans Dijkstra ce cas n'arrive jamais).
Et pour le retrait, on échange le premier et le dernier élément du tas, puis on enlève le dernier, puis on fait "descendre" l'élément racine pour respecter la structure de tas. En l'échangeant avec le minimum de ses enfants.

Et donc tu pourrais dire :

Citation

Tout d'abord, pour bien comprendre l'algorithme, ne vous intéressez pas à la colonne "N°" et au tableau appelé "Tas-File de priorité-Liste ouverte", celui-ci est là pour une optimisation que je vous expliquerai plus tard. Et ignorez également les commentaires en orange

Et en effet, "plus tard" :

Citation

Néanmoins, quand il fallait chercher la ville non déjà parcourue avec le poids (non indéfini) le plus faible, on devait parcourir tout le tableau. Pour 10 villes, ce n'est pas un problème, mais imaginez un grand nombre de ville ! Ainsi on ajoute une structure appelée "liste ouverte" etc.
Et là tu expliques ce qu'est un tas (ou faire des références sur le tuto tri par tas ou encore wikipédia

) Et expliquer les manoeuvres à rajouter pour garder le tas correct. (Les 3 manoeuvres en $O(log(n))$ )
...
Je vous conseille mainteant de relire l'exemple en s'intéressant au tableau "Tas - File de priorité - Liste ouverte" ainsi qu'aux commentaires en orange.

Et donc il suffira de rajouter une ligne à l'algo : quand on change le poids d'une ville, on l'ajoute à la liste ouverte si elle n'y est pas déjà, et on applique l'algorithme 'Modification d'un poids".

Ainsi par exemple, l'étape suivante serait :

Secret (cliquez pour afficher)

Et on recommence ! On recherche le noeud non visité avec le poids le plus faible !

Il s'agit de Paris. On enlève Paris du tas.

On liste les fils

Arras
- Est-on déjà passé par Arras ?
  => Non
- kilométrage de Arras > kilométrage de Paris + distance Paris-Arras ?
  OU
  kilométrage de Arras non défini (= -1) ?
  => Oui :
  - kilométrage de Arras = kilométrage de Paris + distance Paris-Arras
  - kilométrage de Arras = 575 + 185 = 760
  - antécédent de Arras = Paris.
  - On met Arras à jour dans le tas.
Nantes
- Est-on déjà passé par Nantes ?
  => Oui
Brest
- Est-on déjà passé par Brest ?
  => Non
- kilométrage de Brest > kilométrage de Paris + distance Paris-Brest ?
  OU
  kilométrage de Brest non défini (= -1) ?
  => Non
Poitiers
- Est-on déjà passé par Poitiers ?
  => Oui
Lyon
- Est-on déjà passé par Lyon ?
  => Non
- kilométrage de Lyon > kilométrage de Paris + distance Paris-Lyon ?
  OU
  kilométrage de Lyon non défini (= -1) ?
  => Oui :
  - kilométrage de Lyon = kilométrage de Paris + distance Paris-Lyon
  - kilométrage de Lyon = 575 + 465 = 1040
  - antécédent de Lyon = Paris.
  - On met Lyon à jour dans le tas : vu qu'il n'y est pas, on l'y ajoute.

Et puis tu rajoutes, en "secret", les manipulations du tas :

Secret (cliquez pour afficher)

Observation des manipulations du tas :

Il a fallu :

Enlever Paris du tas (étant le minimum)
Mettre Arras à jour.
Ajouter Lyon.

Et donc, notre tas :

Tas - File de priorité - Liste ouverte
Paris (575)
Brest (632)		Arras (895)
Montpellier (794)	Aucune	Aucune	Aucune

Enlever Paris du tas (étant le plus petit poids). 3 étapes :
- Echanger Paris (premier) et Montpellier (dernier)
- Enlever Paris (dernier)
- Descendre Montpellier (premier). Tant que c'est nécessaire.
  - Enfant de Montpellier avec le plus petit poids ? Brest.
  - Poids de Brest plus petit que celui de Montpellier ? Oui.
  - On échange Montpellier et Brest.
Tas - File de priorité - Liste ouverte

Brest (632)

Montpellier (794)

Arras (895)

Aucune

Aucune

Aucune

Aucune
Mettre Arras à jour. Nouveau poids : 760. 1 étape :
- Monter Arras : Tant que Arras a un poids plus faible que son parent, on l'échange avec son parent.
Tas - File de priorité - Liste ouverte

Brest (632)

Montpellier (794)

Arras (760)

Aucune

Aucune

Aucune

Aucune
Ajouter Lyon. 2 étapes :
- Mettre Lyon en dernier.
- Monter Lyon : Tant que Lyon a un poids plus faible que son parent, on l'échange avec son parent.
Tas - File de priorité - Liste ouverte

Brest (632)

Montpellier (794)

Arras (760)

Lyon (1040)

Aucune

Aucune

Aucune

Et donc, les tableaux sont à jours !

Secret (cliquez pour afficher)

Noeud	Poids	Visité	Antécédent	N°
Arras	760	Non	Paris	2
Bordeaux	0	Oui	Aucun	-
Brest	632	Non	Nantes	0
Lyon	1040	Non	Paris	3
Marseille	-1	Non	Aucun	-
Montpellier	794	Non	Poitiers	1
Nantes	334	Oui	Bordeaux	-
Paris	575	Oui	Poitiers	-
Poitiers	237	Oui	Bordeaux	-
Strasbourg	-1	Non	Aucun	-

Remarquons quand même que, si on fait par exemple n changement(s) de poids par tour, le choix du tas ne fait qu'empirer la complexité.
Donc il faut se poser la question si la liste ouverte devrait être un tas ou une liste (chaînée) :

Insertion : $O(log(n))$ contre $O(1)$
Changer un Poids : $O(log(n))$ contre $O(1)$
Enlever le minimum : $O(log(n))$ contre $O(n)$

Ce qui est sûr c'est qu'il serait intéressant de parler de liste ouverte qui s'agrandit et se rapetisse !

Et sinon, tu peux faire un lien vers des structures plus complexes (pour ceux qui veulent optimiser encore plus.

Personnelement je connais juste le tas de Fibonnacci :

Insertion : $O(1)$
Changer un Poids : $O(1)$ amorti
Enlever le minimum : $O(log(n))$ amorti

En résumé

Ce serait intéressant d'ajouter une liste ouverte, pour cela, il suffit de rajouter un nouveau tableau (comme celui que j'ai donné).
Et ensuite de proposer la gestion de cette liste : liste chaînée ou tas-min. Avec une préférence pour le tas si on en croit les commentaires.

(Et je pense aussi qu'un tas sera mieux qu'une liste chaînée ici, mais puisque je n'ai pas démontré cela... Je ne peux rien affirmer.)

Voilà, Qu'en penses-tu ?

Megaz, un Zér0 du Nord du Nord de la francophonie européenne

Mes tutos :

Les Conteneurs de la STL (C++)
Mystérieuses coordonnées hexagonales (en validation).

feaithil

# Posté le 22/08/2011 à 03:00:14

Ville : Pont audemer
Pays : France métropolitaine

Citation : Traize

Disclaimer : ceci est une explication vulgarisée et approximative

A* ne trouve pas forcement le même chemin que Dijkstra. A* trouve généralement la même chose que Dijkstra, mais pas toujours.
De par son évaluation heuristique, il trouve une solution bonne, mais pas optimale à chaque fois. Sa force est de trouver cette "bonne" solution rapidement et à peu de complexité.
A* se dirige "dans la direction de là ou il doit aller" en plaçant des nœuds en priorité dans la liste des nœuds à examiner, et si cela ne marche pas, en examinant les autres noeuds.
Si jamais il trouve un chemin en n'utilisant que ces noeuds prioritaire, il retourne ce chemin, qui semble être le meilleur, puisque "en ligne droite", mais pas forcement le plus court (imaginons le cas d'un labyrinthe...).
Dijkstra lui examine systématiquement le cout de chaque noeud (et non pas une liste de noeuds prioritaires) a chaque "itération", il a donc une bien plus grande complexité (là encore selon l'heuristique), et est plus gourmand en mémoire, en etant plus lent.

Fin du disclaimer

Sympa l'article!
par contre: En choisissant une heuristique qui estimera un coût inférieur au coût final (heuristique suboptimale) (référence: Dechter, R., & Pearl, J. (1985). Generalized best-first search strategies and the optimality af A*. Journal of the ACM, 32(3), 505-536. doi:10.1145/3828.3830)

L'algorithme A* a d'ailleurs une même compléxité dans le pire des cas que djikstra (dépendant du type de donné utilisé) mais par contre une bien meilleur complixité moyenne!

benmic

# Posté le 23/01/2012 à 12:03:28

Hello l'article de base est assez ancien à présent, mais il m'a été bien utile à la compréhension de l'algo... pas comme Wikipedia

Pour ceux que cela intéresse, j'ai fait une implémentation php5.3+ de l'algorithme, que vous pouvez trouver sur https://github.com/bmichotte/php5-Dijkstra

Benjamin

raed

# Posté le 07/05/2012 à 12:26:21

Avis : Bon

Ville : Djibouti
Pays : Djibouti

Salut les amis.
j'ai une question hors-tuto mais dans les théories de graphe.
Voila, comment peut on avoir des arêtes avec des poids négatifs.
Exemple: http://perso.telecom-paristech.fr/~hud [...] n/graphe1.gif

et si vous avez un cours sur l'algorithme de bellman, sa sera gentil

Voir tous les commentaires

Ce tutoriel a été corrigé par les zCorrecteurs.

Les cours phares

Tous les cours par catégories

Autres

Programmation (263 Cours)

Graphisme (29 Cours)

Bureautique (27 Cours)

Jeux Vidéo (18 Cours)

Matériel (7 Cours)

Dernières annonces

Recrutement à Bac / Bac +1

Recrutement à Bac +2

Recrutement à Bac +3 / Bac +4

Recrutement à Bac +5

Dynamisez vos sites web avec JavaScript

Créez des applications pour iPhone, iPad et iPod Touch

Cours

Nouveau ?

Nouveautés

Site Web

Programmation

Bases de données

Mobiles

Systèmes d'exploitation

Graphisme

Infographie 3D

Bureautique

Réseaux

Matériel

Mapping

Le pathfinding avec Dijkstra

Histoire de l'algorithme et de son inventeur

Principe de l'algorithme de Dijkstra

Prérequis

Le principe

Étapes de l'algorithme de Dijkstra

0) Tout d'abord on initialise les tableaux

1) On recherche le noeud non parcouru ayant le poids le plus faible et on indique donc qu'on l'a parcouru

2)On va rechercher ce que l'on appelle "les fils" du noeud où l'on se trouve

3) On boucle en retournant à l'étape 1) tant que...

On initialise les tableaux

On recherche le noeud avec le plus petit poids

On liste les fils de Bordeaux

Aperçu des tableaux

Et on recommence ! On recherche le noeud non entouré avec le poids le plus faible

On liste ses fils

Aperçu des tableaux

Et on recommence ! On recherche le noeud non entouré avec le poids le plus faible

On liste ses fils

Aperçu des tableaux

Partager

Infini

Liste ouverte

Et on recommence ! On recherche le noeud non visité avec le poids le plus faible !

On liste les fils

Observation des manipulations du tas :

En résumé