Scribd
Importer
196 vues11 pages

Algorithme Dijkstra : Chemin Optimal

L'algorithme de Dijkstra permet de trouver le plus court chemin entre un nœud de départ et tous les autres nœuds d'un graphe pondéré. Il fonctionne de manière gloutonne en attribuant initialement une distance infinie à tous les nœuds sauf le départ, puis en mettant à jour les distances à mesure que de nouveaux chemins plus courts sont trouvés.

Transféré par

Victor Houindo
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
196 vues11 pages

Algorithme Dijkstra : Chemin Optimal

L'algorithme de Dijkstra permet de trouver le plus court chemin entre un nœud de départ et tous les autres nœuds d'un graphe pondéré. Il fonctionne de manière gloutonne en attribuant initialement une distance infinie à tous les nœuds sauf le départ, puis en mettant à jour les distances à mesure que de nouveaux chemins plus courts sont trouvés.

Transféré par

Victor Houindo
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Algorithme de Moore-Dijkstra

Méthode du plus court chemin


Plan
1. Le problème du plus court chemin

2. L’Algorithme de Dijkstra
2.1 Principe de l’algorithme
2.2. Pourquoi utiliser cet algorithme ?
2.3. Pseudo-Algorithme
2.4. Application

2
1. Le problème du plus court chemin

● le problème algorithmique qui consiste à trouver un chemin d'un sommet à un


autre de façon que la somme des poids des arcs de ce chemin soit minimale.
3
2. L’Algorithme de Dijkstra
❏ Principes de l’algorithme

● algorithme de recherche de chemin le plus court dans un graphe pondéré


● utilise une approche gloutonne pour trouver le chemin optimal.
● Attribue initialement une distance infinie à tous les nœuds, sauf au nœud de
départ qui a une distance de 0.

L’algorithme détermine le chemin le plus court entre un nœud de départ et tous les autres
nœuds du graphe.

4
2. L’Algorithme de Dijkstra
❏ Pourquoi utiliser Dijkstra ?
● l’algorithme est relativement efficace. Cette complexité est raisonnable même pour
des graphes de grande taille

● garantit la découverte du chemin le plus court entre un nœud de départ et tous les
autres nœuds accessibles du graphe

● offre une simplicité d’implémentation dans le sens où il est relativement simple à


comprendre et à mettre en œuvre.

5
2. L’Algorithme de Dijkstra
/* Itérations */
tant que provisoires ≠ ∅
❏ Pseudo Algorithme soit x ∈ provisoires tel que m(x) est minimum
sur provisoires ;
calculés = calculés ∪ {x} ;
/* Initialisations */
provisoires = provisoires - {x} ;
calculés = {A} ;
pour tout sommet y successeur de x
m(A) = 0 ;
cas
provisoires = ∅ ;
y ∈ calculés : rien
pour tout sommet y successeur de A
y ∈ provisoires :
provisoires = provisoires ∪ {y}
si m(x) + v(x,y) < m(y)
;
m(y) = m(x) v(x,y) ;
m(y) = v(A,y) ;
p(y) = x ;
p(y) = A ;
fsi
fpour
autrement :
provisoires = provisoires ∪ {y} ;
m(y) = m(x) + v(x,y) ;
p(y) = x ;
fcas
fpour
ftantque
/* les sommets n'appartenant pas à calculés
sont inaccessibles */

6
2. L’Algorithme de Dijkstra
❏ Application

7
2. L’Algorithme de Dijkstra
❏ Résolution manuelle

Le chemin trouvé est E -> B -> C -> D -> B-> S

8
2. L’Algorithme de Dijkstra
❏ Résolution avec implémentation en Python

9
2. L’Algorithme de Dijkstra
❏ Domaines d’utilisation

● Utilisé dans les applications de routage dans les réseaux de


télécommunications,

● la planification de trajets dans les systèmes de transport

● d’autres domaines où la recherche de chemins optimaux est nécessaire.

10
Merci pour votre Attention

Vous aimerez peut-être aussi