L’algorithme de Dijkstra utilise une file de priorité (plus exactement un tas-min.
L’algorithme de Dijkstra
Principe
L’algorithme de Dijkstra est un algorithme de parcours de graphe. Il prend en arguments un graphe pondéré et un sommet initial. L’idée de l’algorithme est de parcourir tous les sommets atteignables à partir du sommet initial, du plus proche (au sens du plus court chemin) au plus éloigné.
Il ne fonctionne pas sur tous les graphes. En particulier dans le cadre du cours nous nous restreindrons aux graphes ayant des arêtes de poids strictement positif.
L’idée est simple : puisque l’algorithme visite les sommets par éloignement croissant au sommet initial, un sommet visité plus tard ne peut pas permettre de trouver un chemin plus court pour se rendre à un sommet visité plus tôt.
Souvent, pour expliquer l’idée de Dijkstra, on demande d’imaginer un robinet d’eau que l’on ouvrirait au sommet de départ et qui coulerait dans toutes les directions données par les arêtes du graphe à une vitesse inversement proportionnelle au poids des arêtes. L’algorithme consiste alors à visiter les sommets du graphe au fur et à mesure que l’eau s’y rend.
L’algorithme
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
# This Python module provides an efficient implementation for priority queues import heapq # Utility function that inserts an element to the min-heap, or replaces it otherwise def insertOrReplace (minHeap, element, weight) : # Insert if does not exist if element not in [x[1] for x in minHeap] : heapq.heappush(minHeap, (weight, element)) # Replace otherwise else : indexToUpdate = [x[1] for x in minHeap].index(element) minHeap[indexToUpdate] = (weight, element) heapq.heapify(minHeap) ################################################################### # Dijkstra takes as an input a source node and a graph # It outputs the lengths of the shortest paths from the initial node to the others def dijkstra (graph, sourceNode) : # We first initialize the useful data structures # Distances is the result of the algorithm, with the lengths of the path from the source node to node i # MinHeap is a min-heap that will store the nodes to visit and the associated weight # If a node is not in minHeap, it has been visited # We initialize the algorithm with the source node at distance 0 distances = [float("inf") for i in range(len(graph))] minHeap = [(0, sourceNode)] distances[sourceNode] = 0 # Main loop while len(minHeap) != 0 : # We extract the closest node from the heap (closestNodeDistance, closestNode) = heapq.heappop(minHeap) # We update the distance to the neighbors of this node for (neighbor, weight) in graph[closestNode] : neighborDistance = closestNodeDistance + weight if neighborDistance < distances[neighbor] : insertOrReplace(minHeap, neighbor, neighborDistance) distances[neighbor] = neighborDistance # We return the distances return distances ################################################################### # Test graph graph = [[(1, 1), (2, 7), (5, 3)], [(0, 1), (2, 1), (5, 1)], [(0, 7), (1, 1)], [(4, 2), (5, 2)], [(3, 2), (5, 5)], [(0, 3), (1, 1), (3, 2), (4, 5)]] result = dijkstra(graph, 0) print(repr(result)) |
Dans cet exemple, le graphe utilisé est le suivant, où le sommet source est 0 (représenté sous forme d’un tableau de paires (voisin, poids)) :
Routage
L’algorithme tel qu’il a été décrit nous donne la longueur des chemins, mais pas les chemins eux-mêmes.
Pour obtenir les chemins, on utilise ce qu’on appelle un routage. Un routage est un ensemble d’indications permettant de retrouver facilement les chemins que l’on cherche. Dans le cas de Dijkstra, le routage se lit à l’envers, c’est-à-dire qu’on va préférer indiquer les chemins de la destination à l’origine. L’inverse est aussi possible, mais un peu plus compliqué à réaliser.
Dans le cas de Dijkstra, le routage s’implémente simplement en créant une structure de données indiquant pour chaque sommet (sauf le sommet initial) quel autre sommet doit être emprunté par un chemin de longueur minimale juste avant lui. Plus concrètement, il suffit de se souvenir des prédécesseurs de chaque sommet via le plus court chemin y arrivant.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
# This Python module provides an efficient implementation for priority queues import heapq # Utility function that inserts an element to the min-heap, or replaces it otherwise def insertOrReplace (minHeap, element, weight) : # Insert if does not exist if element not in [x[1] for x in minHeap] : heapq.heappush(minHeap, (weight, element)) # Replace otherwise else : indexToUpdate = [x[1] for x in minHeap].index(element) minHeap[indexToUpdate] = (weight, element) heapq.heapify(minHeap) ################################################################### # Dijkstra takes as an input a source node and a graph # It outputs the lengths of the shortest paths from the initial node to the others def dijkstra (graph, sourceNode) : # We first initialize the useful data structures # Distances is the result of the algorithm, with the lengths of the path from the source node to node i # MinHeap is a min-heap that will store the nodes to visit and the associated weight # If a node is not in minHeap, it has been visited # We initialize the algorithm with the source node at distance 0 distances = [float("inf") for i in range(len(graph))] minHeap = [(0, sourceNode)] distances[sourceNode] = 0 predecessors = [None for i in range(len(graph))] # <-- new code (we keep track of the predecessors of every node along the shortest paths) # Main loop while len(minHeap) != 0 : # We extract the closest node from the heap (closestNodeDistance, closestNode) = heapq.heappop(minHeap) # We update the distance to the neighbors of this node for (neighbor, weight) in graph[closestNode] : neighborDistance = closestNodeDistance + weight if neighborDistance < distances[neighbor] : insertOrReplace(minHeap, neighbor, neighborDistance) distances[neighbor] = neighborDistance predecessors[neighbor] = closestNode # <-- new code (we update the predecessor since the path is shorter when going through the closest node) # We return the distances and the predecessors return (distances, predecessors) # <-- new code (we also return the routes) ################################################################### # Test graph graph = [[(1, 1), (2, 7), (5, 3)], [(0, 1), (2, 1), (5, 1)], [(0, 7), (1, 1)], [(4, 2), (5, 2)], [(3, 2), (5, 5)], [(0, 3), (1, 1), (3, 2), (4, 5)]] (result, routes) = dijkstra(graph, 0) print(repr(result)) print(repr(routes)) |
Si on exécute ce programme, on obtient les résultats suivants :
- result = [0, 1, 2, 4, 6, 2].
- routes = [None, 0, 1, 5, 3, 1].
Cela signifie que pour aller du sommet 0 au sommet 4 par exemple, il faudra au minimum 6 unité de distance (result[4]). Pour déterminer à quel chemin dans le graphe cela correspond, on regarde la table de routage. On a routes[4] = 3. Cela signifie que le prédécesseur du sommet 4 sur un plus court chemin est le sommet 3. On cherche donc ensuite le prédécesseur du sommet 3 : routes[3] = 5. Puis, le prédécesseur du sommet 5 est routes[5] = 1. Enfin, le prédécesseur du sommet 1 est routes[1] = 0. Un plus court chemin de 0 à 4 est donc 0 – 1 – 5 – 3 – 4 pour une taille de 1 + 1 + 2 + 2 = 6.
Complexité
La complexité de l’algorithme dépend fortement de la file de priorité utilisée.
On peut montrer qu’on peut atteindre O(|E| + |V|ln(|V|) en pratique. Dans le cadre du cours où le graphe est un labyrinthe et chaque sommet ne peut avoir que 4 voisins au maximum, on obtient donc une complexité O(|V|ln(|V|), car |E| < 4|V|. Cette complexité est moins que quadratique en le nombre de sommets du graphe, ce qui la rend très raisonnable pour notre application.
Exemple détaillé
Considérons à nouveau le graphe suivant, avec les variables dans leur état initial :
|
1 2 |
distances : [0, ∞, ∞, ∞, ∞, ∞] minHeap : {(node 0, distance 0)} |
La file de priorité n’étant pas vide, on extrait le seul élément qui s’y trouve (le sommet 0), et on regarde tous ses voisins (sommets 1, 2 et 5) :
|
1 2 |
distances : [0, 1, 7, ∞, ∞, 3] minHeap : {(node 1, distance 1), (node 2, distance 7), (node 5, distance 3)} |
L’algorithme cherche ensuite le sommet dans la file de priorité le plus proche. On extrait donc le sommet 1, car à distance minimale, et on regarde tous ses voisins (sommets 0, 2 et 5). Le sommet 0 ayant déjà été visité, y retourner est forcément plus long (notez que ça ne serait pas vrai avec des poids négatifs). Concernant les voisins 2 et 5, il est plus rapide de passer par 1 que d’y aller directement depuis 0. On met donc à jour les distances.
|
1 2 |
distances : [0, 1, 2, ∞, ∞, 2] minHeap : {(node 2, distance 2), (node 5, distance 2)} |
Les deux sommets restants sont à distance égale du sommet source. On en choisit un au hasard. Disons 2. Tous les voisins de 2 sont déjà visités, il n’y a rien de plus à faire.
|
1 2 |
distances : [0, 1, 2, ∞, ∞, 2] minHeap : {(node 5, distance 2)} |
Continuons avec le seul sommet restant : 5. On ajoute ses voisins 3 et 4 aux distances d(0, 5) + d(5, 3) et d(0, 5) + d(5, 4) respectivement.
|
1 2 |
distances : [0, 1, 2, 4, 7, 2] minHeap : {(node 3, distance 4), (node 4, distance 7)} |
Le sommet suivant est le sommet 3. Il est plus court de passer par 3 pour aller à son voisin 4 que d’y aller avec le chemin actuel (passant par 5). On met donc à jour la distance au sommet 4.
|
1 2 |
distances : [0, 1, 2, 4, 6, 2] minHeap : {(node 4, distance 6)} |
On extrait ensuite le seul sommet restant dans la file, qui ne met rien à jour. L’algorithme sarrête ensuite car le tas-min est vide.
|
1 2 |
distances : [0, 1, 2, 4, 6, 2] minHeap : {} |
On remarque que l’algorithme a visité les sommets par distance croissante avec le sommet initial 0.
Correction et terminaison
L’algorithme de Dijkstra termine et est correct si tous les poids dans le graphe considéré sont strictement positifs.
La preuve de correction et de terminaison pour l’algorithme de Dijkstra est plus compliquée que celles que nous avons déjà vues en cours. Nous allons les faire toutes les deux en même temps.
Déjà nous allons admettre avoir une file de priorité dont toutes les opérations terminent et sont correctes.
Pour la preuve, on va procéder par récurrence avec la propriété suivante : “tous les sommets ayant été retirés de la file de priorité sont tels que leurs distances au sommet initial ont été calculées et enregistrées, et les sommets restants s’il en est sont à des distances toutes plus grandes”.
On remarque trivialement que cette affirmation est vraie au premier passage dans la boucle, lorsque l’on retire le sommet initial.
Supposons maintenant cette affirmation vraie à un moment donné lors de l’exécution de l’algorithme. Deux cas : soit la file de priorité est vide, auquel cas l’algorithme s’arrête et la propriété reste donc vraie. Soit un nouveau couple (noeud courant, distance) est retiré de la file de priorité.
On veut montrer que la distance retirée est la distance d’un plus court chemin du sommet initial au sommet courant.
Il nous faut remarquer que déjà il s’agit bien de la distance d’un chemin dans le graphe. En effet, la distance a été mise à jour à un moment où un autre sommet a été retiré auparavant. Par hypothèse de récurrence, cela correspondait bien à un chemin le plus court, et les sommets étant voisins, on obtient bien une quantité correspondant à la longueur d’un chemin.
Ensuite, c’est forcément la distance d’un chemin le plus court. En effet, considérons un chemin le plus court dans le graphe du sommet initial au sommet courant et dénotons “sommet précédent” le sommet immédiatement avant le sommet courant en suivant ce chemin. Par définition du chemin le plus court, le sous-chemin extrait partant du sommet initial au sommet précédent est un chemin le plus court. Ce sous-chemin est strictement plus court car il contient une arête de moins (et les arêtes ont des poids strictement positifs). Par hypothèse de récurrence, le sommet précédent a déjà été retiré de la file de priorité. Et par conséquent la distance au sommet courant a soit été mise à sa valeur minimale à ce moment là, ou y était déjà avant (elle ne pouvait être inférieure puisqu’il s’agit de la distance d’un chemin dans le graphe).
Par récurrence on conclut que la propriété est vraie à toute étape de l’algorithme.
Pour terminer de prouver la correction et avoir en même temps la terminaison, il nous reste à montrer que : a) chaque sommet ne peut-être retiré qu’une seule fois de la file de priorité et b) tout sommet atteignable est retiré au moins une fois.
Pour a), cela se déduit directement de la croissance des distances prouvées dans la récurrence précédente.
Pour b), on remarque que tout sommet atteignable admet un chemin le plus court, et on procède par récurrence le long de ce chemin.