Hétérotopos

Aller au contenu | Aller au menu | Aller à la recherche

L’algorithme de Dijkstra pour les nuls

Pour bien com­pren­dre en quoi les mathé­ma­ti­ques peu­vent nous aider dans ce genre de situa­tion, il con­vient de faire un petit retour en arrière.

konigsberg-efaa1.jpgEn 1736, l’immense Leon­hard Euler résout le pro­blème dit des « 7 ponts de König­sberg  »[1], en modé­li­sant la situa­tion par un « gra­phe » dans lequel les rives de la ville sont notées par des « som­mets », et les ponts par des « arê­tes » joi­gnant ces som­mets. Ce for­ma­lisme ouvre la voie à de nom­breux tra­vaux, comme ceux de William Hamil­ton qui cher­che, vers 1856, un moyen de trou­ver le che­min per­met­tant de pas­ser une fois et une seule par tous les som­mets d’un gra­phe.[2] Mais il fau­dra atten­dre les années 1930 pour que les gra­phes ces­sent d’être des curio­si­tés mathé­ma­ti­ques au sein d’autres dis­ci­pli­nes et s’orga­ni­sent en une véri­ta­ble théo­rie géné­rale, puis la seconde moi­tié du XXème siè­cle pour que des fon­da­tions soli­des soient éta­blies, en par­tie grâce aux recher­ches effec­tuées dans le cadre d’une science en plein essor : l’infor­ma­ti­que théo­ri­que.[3]

axxad-f2b76.jpgNotons que l’his­toire de le théo­rie des gra­phes est inti­me­ment liée aux pro­blè­mes très con­crets aux­quels elle s’est éver­tuée à cher­cher des solu­tions, ce qui en fait aujourd’hui une dis­ci­pline rela­ti­ve­ment sim­ple à ensei­gner : son for­ma­lisme plu­tôt « natu­rel » ne rebute pas les esprits habi­tuel­le­ment her­mé­ti­ques aux mathé­ma­ti­ques, ses nom­breu­ses appli­ca­tions en font un outil appré­cia­ble de recher­che opé­ra­tion­nelle (com­mu­né­ment appe­lée “aide à la déci­sion”), et sa proxi­mité avec l’infor­ma­ti­que la pare des attri­buts de cette moder­nité que la déma­go­gie péda­go­gi­que se plaît à con­fon­dre avec le pro­grès. Il serait cepen­dant erroné de croire que c’est pour autant une dis­ci­pline sim­ple, et nous retien­drons que cer­tains pro­blè­mes appa­rem­ment élé­men­tai­res atten­dent encore leurs solu­tions.[4] D’autres, cepen­dant, ont été réso­lus de manière élé­gante, et c’est le cas de celui qui nous inté­resse ici : la recher­che du plus court che­min.

Par­tons d’un cas con­cret : un auto­mo­bi­liste doit se ren­dre de Troyes à Autun. Si vous obser­vez la carte ci-des­sous, vous remar­quez qu’un fais­ceau de tra­jec­toi­res pos­si­bles s’offre à lui : il peut pas­ser par St Flo­ren­tin, Ton­nerre, Cha­tillon, Mont­bard, Auxerre, Sens, Sau­lieu, Dijon, Beaune. Selon qu’il cher­che à limi­ter son kilo­mé­trage ou son temps de par­cours, sa con­som­ma­tion ou le coût total du tra­jet, il peut sou­hai­ter ne rou­ler que sur des natio­na­les, que sur l’auto­route, ou alter­ner les deux. Qui plus est, alerté sur la den­sité du tra­fic, il peut être amené à effec­tuer des choix plus com­plexes.

carte-f6aee.jpg
La pre­mière par­tie du tra­vail va con­sis­ter à cons­truire un gra­phe, le plus pré­cis et le plus large pos­si­ble de la situa­tion. Pour cela, com­men­çons par nom­mer les vil­les par des let­tres, et repor­tons ces let­tres dans un tableau à deux entrées, comme ci-des­sous.

table-bda4c.jpg
Ensuite, atta­quons-nous à la par­tie peut-être la plus impor­tante : la pon­dé­ra­tion du gra­phe. Il s’agit de fixer les cri­tè­res per­ti­nents de l’opti­mi­sa­tion (la dis­tance, le temps, le coût, une com­bi­nai­son de ces para­mè­tres…) et de cal­cu­ler la « dis­tance » entre les som­mets au sens de ces cri­tè­res. Fai­sons par exem­ple l’hypo­thèse que nous con­nais­sons par­fai­te­ment l’état du tra­fic sur l’ensem­ble de ce réseau, et créons arbi­trai­re­ment un « coef­fi­cient de tra­fic » entre 1 et 100, la valeur 1 signi­fiant que le tra­fic est par­fai­te­ment fluide (et donc que nous pou­vons rou­ler à la vitesse maxi­male auto­ri­sée).

Par exem­ple :

  1. la dis­tance Ton­nerre - Cha­tillon est de 49 km. Il s’agit d’une natio­nale, ce qui signi­fie que nous pou­vons rou­ler à 90 km:h, soit un temps de tra­jet de 0,54 h. Mais le tra­fic légè­re­ment per­turbé nous amène à pon­dé­rer ce tra­jet d’un coef­fi­cient 7, soit une « dis­tance », à notre sens, de 0,57 x 7 = 3,8 arrondi à 4.
  2. la dis­tance Cha­tillon - Mont­bard est de 33 km. Il s’agit éga­le­ment d’une natio­nale, le temps de tra­jet est donc de 0,37 h. Mal­heu­reu­se­ment, le tra­fic est extrê­me­ment dif­fi­cile, et nous déci­dons de pon­dé­rer ce tra­jet d’un coef­fi­cient 57, soit une « dis­tance » de 0,37 x 57 = 21.
  3. répé­tons ce cal­cul pour l’ensem­ble des tra­jets per­ti­nents, et ima­gi­nons[5] que nous obte­nons le tableau sui­vant :


table2-b0c0f.jpg

tableau qui cor­res­pond au gra­phe sui­vant :
dij-9a4c3.jpg
Nous allons main­te­nant appli­quer l’algo­rithme de Dijks­tra à ce gra­phe. Plu­tôt que de lon­gues expli­ca­tions théo­ri­ques, j’ai décidé d’enre­gis­trer la réso­lu­tion, à la main, sur la vidéo sui­vante. Je vous con­seille vive­ment de vous munir d’un crayon et d’un papier pour effec­tuer le cal­cul en même temps que moi…


Le tra­jet le plus « court », au sens de notre pon­dé­ra­tion sem­ble donc être le tra­jet CAFHJI, soit : Troyes - Ton­nerre - Auxerre - Dijon - Beaune -Autun.
L’algo­rithme de Dijks­tra[6] a été publié en 1959. C’est un algo­rithme de type « glou­ton »[7], et il est l’un des plus effi­ca­ces pour trai­ter les pro­blè­mes de plus court che­min[8] : sa sim­pli­cité per­met son ensei­gne­ment dans la spé­cia­lité “Mathé­ma­ti­ques” des clas­ses de Ter­mi­nale ES. Grâce à la puis­sance du trai­te­ment infor­ma­ti­que, il est uti­lisé par les logi­ciels d’opti­mi­sa­tion de tra­jets réels (Navi­ga­teurs GPS, Site R.A.T.P….) ou vir­tuels (rou­tage inter­net).

Si vous êtes inté­res­sés par cette dis­ci­pline, je vous con­seille de sui­vre les liens sui­vants :

  1. le petit dos­sier réa­lisé par l’excel­lent site Inters­ti­ces.
  2. un excel­lent cours en Pdf, très com­plet, sur la Théo­rie des Gra­phes.
  3. et enfin une jolie applet Java qui per­met de des­si­ner ses pro­pres gra­phes, les pon­dé­rer, et les résou­dre gra­phi­que­ment pas à pas.

Notes

[1] Si vous com­pre­nez le latin, vous pou­vez lire la démons­tra­tion dans le traité ori­gi­nal.

[2] Vous con­nais­sez pro­ba­ble­ment un exem­ple sim­ple de ce pro­blème : la petite mai­son que l’on des­sine sans jamais lever le crayon.

[3] Nous retien­drons entre autres les tra­vaux remar­qua­bles de Karl Men­ger , d’Arthur Cay­ley , de Claude Berge et du légen­daire Paul Erdös .

[4] Comme le fameux Tra­vel­ling Sales­man Pro­blem (ou Pro­blème du Voya­geur de Com­merce) pour un grand nom­bre de vil­les.

[5] J’ai modi­fié les don­nées pour créer un gra­phe plus inté­res­sant à trai­ter, vous ne m’en tien­drez pas rigueur !

[6] Du nom de son inven­teur, Edsger Dijks­tra, mathé­ma­ti­cien et infor­ma­ti­cien néer­lan­dais décédé en 2002.

[7] Pour résu­mer, une fois qu’un som­met a été traité, l’algo­rithme n’y revient plus.

[8] Mais il en existe de nom­breux autres, plus spé­ci­fi­ques, dont vous trou­ve­rez la liste ici.

Evrim Evci

Auteur: Evrim Evci

Restez au courant de l'actualité et abonnez-vous au Flux RSS de cette catégorie

Commentaires (0)

Les commentaires sont fermés


aucune annexe



À voir également

arton31.jpg

Le lambda-calcul pour les nuls

L’obs­cur fonc­tion­naire du dépar­te­ment Jeu­nesse & Sports de la mai­rie d’Alfort­ville qui, en ce magni­fi­que mois d’août 1982, avait décidé de met­tre une ving­taine de Thom­son TO7-70 en libre accès, afin de per­met­tre aux jeu­nes désœu­vrés que nous étions de venir goû­ter aux joies de l’infor­ma­ti­que per­son­nelle nais­sante, se dou­tait-il de l’avan­tage déci­sif qu’allait nous pro­cu­rer cette ini­tia­tive ?

Lire la suite