Algorhytme de Dijsktra
Après avoir étudié le problème du chemin minimum qui est lié aux graphes hamiltoniens, on va étudier un autre algorithme qui a un bout pareil. L'algorithme de Dijkstra, également appelé algorithme des chemins minimaux. Il s'agit d'un algorithme qui sert à déterminer le chemin le plus court étant donné une origine de sommet au reste des sommets d'un graphe avec des poids sur chaque arête. Son nom fait référence à Edsger Dijkstra, qui l'a décrit pour la première fois en 1959. En revanche du problème du chemin minimum, il ne nous permet pas de trouver une route qui passe par tous les sommets du graphe, sinon qu’il cherche le chemin entre deux sommets sans regarder la quantité d'arêtes ni sommets qui à dans le chemin final.
Pour trouver le chemin, il faut tenir en compte tous les chemins possibles. Soit A le sommet de départ, il faudra regarder les distances entre A et la reste de sommets du graphe. Dans le cas où il ne soit pas adjacent à A, on donnera un valeur ∞ à la distance. On devra en tout cas regarder la distance totale jusqu’à le sommet d’origine, tenant en compte les parcours qu’on choisit dans chaque cas. Pour trouver ces chemins on peut faire une table avec les distances et les choix dans chaque cas. On introduira les distances comme (X,v) soit X le poids des arêtes, c'est- à dire la distance entre le vertice d’origine et v, le sommet où on se trouve. Quand un sommet est déjà choisi, on complète sa file dans la table avec des X. On regardera chaque fois le sommet choisi et on trouvera les distances en passant pour eux jusqu’à le sommet de départ.Pour comprendre comment fonctionne l'Algorithme de Dijkstra, on analysera pourquoi le chemin minimum entre A et E c’est C=[AC,CD,DF].
On commence à regarder les distances de A au reste de sommets, puis on répète jusqu'à arriver à F. C’est nécessaire de prouver dans chaque cas si suivant le chemin choisi la distance dès l’origine est plus petite, sinon il faut laisser laquelle on avait déjà trouvé, comme par exemple on peut voir sur la table dans le cas de E, où la distance n'a pas été altérée.
