%% nav-debut : généré par gen_navigation.py, ne pas modifier à la main %%
> [!nav]
> ↩ [[Code et Développement/Programmation/Graphes/Graphes|Accueil · Graphes]]
>
> | [[Code et Développement/Programmation/Graphes/04_Parcours en profondeur (DFS)\|← Parcours en profondeur – DFS]] | |
> |:---|---:|
%% nav-fin %%
# L'algorithme de Dijkstra
L'algorithme de Dijkstra calcule le **plus court chemin** dans un **graphe pondéré** dont les poids sont positifs. Le graphe peut être orienté ou non orienté.
Il calcule les plus courts chemins d'un sommet de départ vers tous les autres sommets. Il sert par exemple à trouver l'itinéraire le plus court entre deux villes, connaissant le réseau routier et la longueur de chaque route.
La longueur d'un chemin est ici la somme des poids de ses arêtes, et non plus le nombre d'arêtes. Le [[Code et Développement/Programmation/Graphes/03_Parcours en largeur (BFS)|parcours en largeur]] ne convient donc plus.
## Le graphe étudié
Le graphe est le graphe de référence pondéré, non orienté. Il est stocké dans un dictionnaire de dictionnaires, au format du chapitre [[Code et Développement/Programmation/Graphes/02_Représentation en Python|Représentation en Python]].
```python
D = {
'A': {'B': {'weight': 12.3}, 'F': {'weight': 14.5}},
'B': {'A': {'weight': 12.3}, 'F': {'weight': 6.1}},
'C': {'D': {'weight': 4.2}, 'E': {'weight': 17.0}, 'F': {'weight': 9.8}},
'D': {'C': {'weight': 4.2}, 'E': {'weight': 3.3}, 'G': {'weight': 10.6}},
'E': {'C': {'weight': 17.0}, 'D': {'weight': 3.3}},
'F': {'A': {'weight': 14.5}, 'B': {'weight': 6.1}, 'C': {'weight': 9.8}, 'G': {'weight': 6.2}},
'G': {'D': {'weight': 10.6}, 'F': {'weight': 6.2}},
}
```
Le graphe est non orienté : chaque arête apparaît dans les voisins de ses deux extrémités. Si l'on dispose d'un graphe `networkx` `G`, `nx.to_dict_of_dicts(G)` produit ce dictionnaire.
**À manipuler :** le dessin, la matrice et le dictionnaire du graphe.
```sq-representation
arêtes: A-B:12.3, B-F:6.1, C-D:4.2, C-E:17.0, C-F:9.8, D-E:3.3, F-G:6.2, F-A:14.5, G-D:10.6
```
## Lire le dictionnaire
`D['A']` donne le dictionnaire des voisins de A. `D['A']['F']['weight']` donne le poids de l'arête A-F. L'opérateur `in` teste la présence d'une clé.
```sq-affiche
# D est le dictionnaire non orienté construit plus haut.
print(sorted(D['A']))
print(D['A']['F']['weight'])
print('X' in D['A'])
print('F' in D['A'])
print('A' in D)
print('X' in D)
---
saisie: lignes
réponse: ['B', 'F']\n14.5\nFalse\nTrue\nTrue\nFalse
explication: sorted(D['A']) donne la liste triée des voisins de A. 'F' in D['A'] teste s'il existe une arête entre A et F. 'A' in D teste si A est un sommet du graphe. X n'est ni un voisin de A ni un sommet.
```
## Le principe
L'algorithme associe à chaque sommet une distance provisoire. Au départ, elle vaut 0 pour le sommet de départ et l'infini pour les autres.
À chaque étape :
1. On choisit, parmi les sommets non fixés, celui dont la distance provisoire est la plus petite. On le note u.
2. On **fixe** u : sa distance ne changera plus.
3. Pour chaque voisin v de u, on calcule la distance de u plus le poids de l'arête u-v. Si cette valeur est plus petite que la distance provisoire de v, elle la remplace, et u devient le **précédent** de v.
L'algorithme s'arrête quand tous les sommets atteignables sont fixés.
Le choix du sommet le plus proche à l'étape 1 garantit le résultat. Tous les poids étant positifs, aucun chemin passant par un sommet plus éloigné ne peut ensuite raccourcir la distance de u.
**À manipuler :** suivez l'algorithme depuis A. Le tableau donne la distance provisoire et le précédent de chaque sommet. À la fin, le plus court chemin de A à E est surligné.
```sq-dijkstra
arêtes: A-B:12.3, B-F:6.1, C-D:4.2, C-E:17.0, C-F:9.8, D-E:3.3, F-G:6.2, F-A:14.5, G-D:10.6
départ: A
arrivée: E
```
## Le programme
```python
def dijkstra(G, debut):
distance = {debut: 0} # distances provisoires des sommets atteints
precedent = {debut: None}
fixes = set()
while True:
# u : sommet non fixé de plus petite distance
u = None
for s in distance:
if s not in fixes and (u is None or distance[s] < distance[u]):
u = s
if u is None: # tous les sommets atteignables sont fixés
break
fixes.add(u)
for v in G[u]:
d = distance[u] + G[u][v]['weight']
if v not in distance or d < distance[v]:
distance[v] = d
precedent[v] = u
return distance, precedent
distance, precedent = dijkstra(D, 'A')
print(distance)
print(precedent)
```
Ce programme affiche :
```
{'A': 0, 'B': 12.3, 'F': 14.5, 'C': 24.3, 'G': 20.7, 'D': 28.5, 'E': 31.8}
{'A': None, 'B': 'A', 'F': 'A', 'C': 'F', 'G': 'F', 'D': 'C', 'E': 'D'}
```
Un sommet absent du dictionnaire `distance` n'est atteint par aucun chemin. Sa distance est infinie.
## Le plus court chemin entre deux sommets
La distance de A à E est `distance['E']`, soit 31.8.
Le chemin se lit en remontant les précédents depuis E : E, D, C, F, A.
```python
def chemin(precedent, fin):
c = [fin]
while precedent[c[-1]] is not None:
c.append(precedent[c[-1]])
c.reverse()
return c
print(chemin(precedent, 'E'), distance['E'])
```
Ce programme affiche :
```
['A', 'F', 'C', 'D', 'E'] 31.8
```
## Une erreur fréquente
Parcourir les sommets dans l'ordre d'une file, comme dans le parcours en largeur, ne suffit pas. Un sommet risque d'être traité avant que sa distance soit définitive. Ses voisins reçoivent alors une distance trop grande, qui n'est jamais corrigée.
Exemple : arêtes A-C de poids 5, A-B de poids 1, B-D de poids 1, D-C de poids 1, C-E de poids 1. Si l'on traite C dès qu'il est découvert depuis A, on donne à E la distance 5 + 1 = 6. Le vrai plus court chemin, A → B → D → C → E, mesure 4.
L'algorithme de Dijkstra évite cette erreur, car il ne traite un sommet que lorsque sa distance est la plus petite de celles qui restent.
```sq-dijkstra
arêtes: A-C:5, A-B:1, B-D:1, D-C:1, C-E:1
départ: A
arrivée: E
```
## Complexité
Pour n sommets, la recherche du sommet le plus proche parcourt jusqu'à n sommets, et elle est répétée n fois. Le programme ci-dessus est donc en O(n²).
Le module `heapq` de Python fournit un tas, qui donne le plus petit élément sans parcourir tous les autres. Avec un tas, l'algorithme est en O((n + a) log n), pour n sommets et a arêtes.
```python
import heapq
def dijkstra_tas(G, debut):
distance = {debut: 0}
tas = [(0, debut)] # couples (distance, sommet)
fixes = set()
while tas:
d, u = heapq.heappop(tas) # sommet de plus petite distance
if u in fixes:
continue
fixes.add(u)
for v in G[u]:
nd = d + G[u][v]['weight']
if v not in distance or nd < distance[v]:
distance[v] = nd
heapq.heappush(tas, (nd, v))
return distance
```
## Avec networkx
La fonction `nx.shortest_path_length` du module `networkx` applique l'algorithme de Dijkstra quand on lui indique l'attribut de poids.
```python
import networkx as nx
G = nx.Graph(D)
print(nx.shortest_path_length(G, 'A', weight='weight'))
print(nx.shortest_path(G, 'A', 'E', weight='weight'))
```
Ce programme affiche :
```
{'A': 0, 'B': 12.3, 'F': 14.5, 'G': 20.7, 'C': 24.3, 'D': 28.5, 'E': 31.8}
['A', 'F', 'C', 'D', 'E']
```
%% nav-debut : généré par gen_navigation.py, ne pas modifier à la main %%
> [!nav]
> ↩ [[Code et Développement/Programmation/Graphes/Graphes|Accueil · Graphes]]
>
> | [[Code et Développement/Programmation/Graphes/04_Parcours en profondeur (DFS)\|← Parcours en profondeur – DFS]] | |
> |:---|---:|
%% nav-fin %%