sur Internet
sur ground418

L'algorithme de Dijsktra

Sommaire:

Histoire
Définitions
L'algorithme
Implentations
Références



Edsger Dijkstra était un mathématicien hollandais. Né en 1930, il fut d'abort des études en physique théorique avant de ce pencher sur les premiers problèmes reliés à l'informatique. Sur une période de plus de 40 ans, sa contribution scientifique fut énorme: plus de 1300 articles totalisant plus de 7700 pages dont la plupart étaient écrit par lui seul (sans co-auteurs). Le plus surprenant c'est qu'il les écrivaient toujours à la main, sans l'aide d'un ordinateur, et envoyait des copies à ses amis par la poste.

Il fut l'un des premiers à se pencher sur le concept de semaphore en 1962. Concept qui est maintenant bien intétégré dans les langages modernes pour la gestion et syncronization des processus. Une excellente biographie est disponible en référence [1].

L'algorithme de Dijsktra est pratique pour résoudre les problèmes de plus court chemin dans les graphes orientés et connexes. Pour bien expliquer cet algorithme, nous devons définir un graph. En mathématique, un graph peut etre orienté ou non orienté. Un graphe est orienté si ses arêtes sont orientés, elles ont donc toutes une direction spécifique. Le graphe ci dessous est donc orienté puisque l'arête pointe sur le sommet B.

A B
Dans un graphe orienté, on nomme le chemin entre 2 sommets X et Y par la suite d'arêtes qu'il faut parcourir depuis X pour atteindre Y.

---

Algorithme

	procéduce Dijkstra (G: graphe simple connexe valué avec toutes les valeurs positives)
	{ G a des sommets a = v0, v1, ..., vn = z et les valeurs w(vi, vj) oú w(vi, vj) = ∞ si { vi, vj } 
		n'est pas un arc dans G }

	pour i := 1 à n
		L(vi) := ∞
	L(a) := 0
	S := ∅
	{ les étiquettes sont initialisées de telle sorte que l'étiquette a est 0, 
		que toutes les autres étiquettes sont ∞ et que S est un ensemble vide }
	tant que z ∉ S
	début
		u := un sommet non dans S avec L(u) minimal
		S := S ∪- {u}
		pour tous les sommets v non dans S
			Si L(u) + w(u, v) < L(v) alors L(v) := L(u) + w(u, v)
		{ cette opération ajoute un sommet à S avec l'étiquette minimale et met à jour 
			les étiquettes des sommets non dans S }
	fin { L(z) = longueur du chemin minimal de a à z }


						

---

Pour conclure, voici une quelques aphorismes propres à Dijkstra:

"L'informatique n'est pas plus la science des ordinateurs que l'astronomie est celle des télescopes."
"L'utilisation de Cobol déforme l'esprit, son enseignement devrait donc �tre considéré comme un crime." [2]

Références

[1] Biographie électronique de Edsger Dijkstra [ http://homepages.cwi.nl/~apt/ps/dijkstra.pdf ]

[2] Utilisé dans "How do we tell truths that might hurt?" de Selected Writings on Computing:A Personal Perspective.

[3] Mathématiques discrètes, édition révisée par Kenneth H. Rosen, 2002, pages 471-473.