#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.