#code #algorithme
L’algorithme de Djisktra permet de trouver le chemin le plus court depuis une source S d’un weighted directional graph.
Pour fonctionner efficacement, l’algorithme de Djisktra nécessite une priority queue.
Les étapes sont :
1. Créer un array shortest
, où shortest[v]
est la distance jusqu’à v
.
2. Mettre toutes les distances à +infini, sauf la source S, qui est à 0.
3. Dans une loop, à l’aide de la priority queue, prendre le vertex le plus proche, le sortir de la priority queue, et mettre à jour tous ses voisins.
Avec n
le nombre de vertices et m
le nombre de edges dans le graph, on dit que :
- Le graph est “dense” si chaque vertices est connectée à presque tous les autres vertices. Dans ce cas, m
est proche de n^2
- Sinon, le graph est “sparse”: m
est du même ordre de grandeur de n
.
Il existe plusieurs implémentations possibles pour une priority queue, et la meilleure pour l’algorithme de Djisktra dépend du graph : si il est dense ou sparse.
Pour un graph dense, un priority queue qui utilise un simple array, non trié sera en O(n^2)
au total: l’opération “extract min” prend n opérations, dans un loop qui est effectuée n fois.
Pour un graph sparse, une priority queue implémentée en binary heap
sera en O(m*log(n))
, donc O(n*log(n))
, car les opérations sur un binary heap prennent log(n)
en moyenne.
Pourquoi ne pas utiliser un binary heap pour un dense graph ? Car dans ce cas, l’étape qui diminue les shortest de tous les voisins du vertex sélectionné prend O(m*log(n)
au total, soit O(n^2*log(n))
. Ce qui est pire que le O(n^2)
d’un simple array.