L'algorithme de Dijsktra : C++, Python Exemple de code
Sarah Chen
Quel est le chemin le plus court ou la distance la plus courte ?
Un chemin allant du sommet source au sommet de destination qui coûte un minimum est le chemin le plus court ou la distance la plus courte. En théorie des graphes, il est possible d’avoir plusieurs itinéraires depuis une source vers une destination. Entre ces itinéraires, s’il existe un itinéraire qui coûte un montant minimum, nous pouvons l’appeler l’algorithme du chemin le plus court.
Ici, « Coût » désigne le nombre de nœuds dans l'itinéraire ou la somme des coûts sur chaque chemin. Un chemin peut avoir un ou plusieurs bords. La connexion entre deux sommets est appelée « arête ». Il existe différents types d'algorithmes de chemin le plus court, comme l'algorithme de Dijkstra, l'algorithme de Bellman-Ford, etc.
Ici, nous discutons de l'algorithme de Dijkstra
Regardons le graphique pondéré suivant :
- Le terme « pondéré » signifie déplacer les coûts d’un nœud à un autre. Par exemple, en passant du nœud 1 au nœud 2, le coût ou le poids est de 1.
- Le chemin entre le nœud 1 et le nœud 2 est appelé le bord.
- « Non dirigé » signifie que vous pouvez déplacer un nœud vers un autre et revenir au nœud précédent. Donc, si nous essayons de trouver toutes les routes du nœud 1 au nœud 7, alors ce sera :
| Itinéraire ou chemin | Prix |
|---|---|
| 1-2-6-7 | (1+3+3) = 7 |
| 1-2-3-7 | (1+9+1) = 11 |
| 1-3-7 | (7+1) = 8 |
| 1-4-5-7 | (6+2+5) = 13 |
Parmi ces quatre itinéraires, nous pouvons voir que le premier itinéraire nous coûtera 7. C'est donc le chemin le plus court en termes de coût.
Comment fonctionne l'algorithme de Dijkstra
L'algorithme de Dijkstra peut trouver la distance la plus courte dans les graphiques pondérés orientés et non orientés. Cet algorithme est gourmand car il choisit toujours le nœud le plus court ou le plus proche de l'origine. Le terme « gourmand » signifie que parmi un ensemble d’issues ou de résultats, l’algorithme choisira le meilleur d’entre eux.
Ici, nous essayons de trouver les chemins les plus courts parmi tous les autres itinéraires. Ainsi, l'algorithme de Dijkstra trouve tous les chemins les plus courts à partir d'un seul nœud de destination. De ce fait, il se comporte comme un algorithme gourmand.
Dans la section « exemple » ci-dessous, vous verrez l'approche étape par étape. Cela fonctionne comme suit :
Étape 1) Initialisez le nœud de départ avec 0 coût et le reste du nœud avec Infinity Cost.
Étape 2) Maintenir un tableau ou une liste pour garder une trace des nœuds visités
Étape 3) Mettez à jour le coût du nœud avec le coût minimum. Cela peut être fait en comparant le coût actuel avec le coût du chemin. (La démonstration est présentée dans la section exemple)
Étape 4) Continuez l'étape 3 jusqu'à ce que tous les nœuds soient visités.
Après avoir complété toutes ces étapes, nous trouverons le chemin qui coûte le moins cher de la source à la destination.
Différence entre Dijkstra et BFS, DFS
La principale différence entre Dijkstra et BFS-DFS est que Dijkstra est l'algorithme de recherche de chemin le plus court et que BFS, DFS est l'algorithme de recherche de chemin. Dans les cas généraux, BFS et DFS ne prennent pas en compte le coût lors de la recherche du chemin. Ces algorithmes ne peuvent donc pas garantir le chemin le plus court.
Démonstration de grille 2D du fonctionnement de BFS
Cette démonstration indique que BFS trouve uniquement le chemin. Toutefois, il ne se soucie pas du poids du chemin. BFS (Recherche en largeur d'abord) suppose que voyager d’un nœud à un autre ne coûtera que 1.
Mais voyons un exemple de graphique :
Ici, il trouve un chemin au niveau 2. BFS parcourt le graphique dans l'ordre des niveaux. Donc ça voyage comme :
Étape 1) Commencez par le nœud « 1 » et visitez tous les nœuds adjacents 2,3,4
Étape 2) Marquez les nœuds 2,3,4 comme niveau 1 et visitez leurs nœuds adjacents. Il continuera à explorer tous les nœuds adjacents jusqu'à ce qu'il atteigne le nœud de destination.
En termes de DFS, il parcourra le chemin de 1 à 7 comme suit :
- 1 → 2 → 3 → 7 (coût initial 10, coût DFS 3)
- 1 → 2 → 6 → 7 (coût initial 7, coût DFS 3)
- 1 → 3 → 7 (coût initial 8, coût DFS 2)
- 1 → 4 → 5 → 7 (coût initial 13, coût DFS 3)
Comme nous le voyons, DFS calcule son coût de chemin avec le nombre de profondeur ou le nombre d'arêtes.
DFS effectue les opérations suivantes :
- DFS peut trouver un chemin depuis la source (sommet de départ) jusqu'à la destination.
- Il ne peut pas garantir si le chemin découvert du nœud source à la destination est le chemin le plus court ou non.
Cependant, en termes d’algorithme de Dijkstra, il choisira les arêtes en fonction de leur coût. En tant qu'algorithme glouton, il sélectionnera les chemins les meilleurs ou les moins coûteux.
Exemple de l'algorithme de Dijkstra
L'algorithme de Dijkstra utilise le coût ou le poids pour calculer le coût total du chemin.
L'objectif de l'algorithme de Dijkstra est de minimiser ce coût ou ce poids total. Dans l'exemple ci-dessus, nous trouvons les meilleurs chemins du nœud 1 au nœud 7, puis calculons tous les coûts.
Dans l'algorithme de Dijkstra, il trouvera les chemins les plus courts en calculant des poids. Il ne cherchera pas tous les chemins possibles. Démontrons l'algorithme de Dijkstra avec un exemple. Par exemple, il vous a été demandé de trouver le chemin le plus court entre le nœud 1 et le nœud 7.
Pour ce processus, les étapes sont indiquées ci-dessous :
Étape 1) Initialisez le coût du nœud de départ à 0.
Reste du nœud, attribuer « Inf ». Cela signifie qu'aucun chemin n'existe entre le sommet de départ (la source) et le nœud, ou que le chemin n'est pas encore visité.
Étape 2) Lorsque vous sélectionnez le nœud 1, il sera marqué comme visité. Mettez ensuite à jour tous les voisins adjacents du nœud 1. 2,3,4 sont les nœuds voisins du nœud 1.
Lors de la mise à jour d'un coût, nous devons suivre la procédure ci-dessous :
Nous pouvons mettre à jour le coût de chaque nœud en utilisant la formule ci-dessus. Par exemple, nous étions au nœud 1 et nous devions mettre à jour le coût de son nœud adjacent 2,3,4.
Après la mise à jour, le coût ou le poids ressemblera à ceci :
Étape 3) Pour le nœud « 2 », les voisins sont 6 et 3. Nous mettons à jour le coût à « 6 » en comparant l'infini (valeur actuelle). Le coût du nœud 2 + le coût du chemin de 2 à 6. En termes simples, le nœud « 6 » aura le coût de 1+3 ou 4.
Le nœud 3 est voisin du nœud 2. Cependant, nous avons calculé son coût à l'étape précédente, qui était de 7. Maintenant, si notre chemin est 1-2-3, le nœud 3 aura un coût de 10. Chemin 1-2- 3 coûtera 10, tandis que 1 à 3 coûtera 7.
Étape 4) Pour le nœud 3, le nœud voisin est 7. Ainsi, en comparant la valeur actuelle du nœud 7 avec le coût du chemin (7+1) ou 8, nous mettrons à jour le coût du nœud 7. Soit 8.
Nous trouvons donc un chemin du nœud 1 au nœud 7, et il vaut 1 → 3 → 7. Le coût est de 8.
Étape 5) Pour le nœud 4, nous mettrons à jour son coût de nœud adjacent en conséquence. Ainsi, le nœud « 5 » aura un coût mis à jour de 8. Après l'étape 4,5, il ressemblera à ceci :
Désormais, le chemin 1-3-7 coûte 8 (auparavant). Le nœud « 7 » n'a pas été marqué comme visité car nous pouvons atteindre le nœud « 7 » à partir du nœud « 6 ». Le chemin « 1-2-6 » avait un coût de 4. Le chemin 1-2-6-7 aura donc un coût de 7.
Comme 7 < 8, c'est pourquoi le chemin le plus court du sommet source « 1 » au sommet de destination « 7 » sera 1-2-6-7, et le coût est 7. Auparavant, c'était 1-3-7, et le coût avait 8 ans.
Ainsi, le graphique final ressemblera à ceci :
Le bord marqué d'une ligne noire est notre chemin le plus court de 1 à 7, et il nous en coûtera 7.
Algorithme du pseudo-code Dijkstra
Voici le pseudo-code de l'algorithme de Dijkstra
Dijkstra(G, S):
for each vertex V in G
distance[V] & lt; - Infinity
previous[V] & lt; - NULL
if V does not equal S, then,
(priority queue) Q.push(V)
distance[S] = 0
While Q is not empty
U & lt; - Extract the MIN from Q
For each unvisited adjacent V of U
TotalDistance & lt; - distance[U] + edge_cost(U, V)
if TotalDistance is less than distance[V], then
distance[V] & lt; - TotalDistance
previous[V] & lt; - u
return distance, previous
C++ implémentation de l'algorithme de Dijkstra
Pour implémenter l'algorithme de Dijkstra en utilisant C++, voici le code :
#include <bits/stdc++.h>
using namespace std;
#define size 7
int minimumDistance(int distance[], bool visited[]) {
int min = INT_MAX;
int min_index = INT_MAX;
for (int i = 0; i < size; i++) {
if (!visited[i] & amp; & distance[i] <= min) {
min = distance[i];
min_index = i;
}
}
return min_index;
}
void printParentPath(int parent[], int i) {
if (parent[i] == -1) {
return;
}
printParentPath(parent, parent[i]);
cout << i + 1 << " ";
}
void dijkstra(int graph[size][size], int source) {
int distance[size];
bool visited[size];
int parent[size];
for (int i = 0; i < size; i++) {
parent[0] = -1;
distance[i] = INT_MAX;
visited[i] = false;
}
distance[source] = 0;
for (int i = 0; i < size - 1; i++) {
int U = minimumDistance(distance, visited);
visited[U] = true;
for (int j = 0; j < size; j++) {
int curr_distance = distance[U] + graph[U][j];
if (!visited[j] & amp; & graph[U][j] & amp; &
curr_distance < distance[j]) {
parent[j] = U;
distance[j] = curr_distance;
}
}
}
cout << "Vertex\t\tDistance\tPath" << endl;
for (int i = 1; i < size; i++) {
cout << source + 1 << "->" << i + 1 << "\t\t" << distance[i] << "\t\t"
<< source + 1 << " ";
printParentPath(parent, i);
cout << endl;
}
}
int main() {
int graph[size][size] = {{0, 1, 7, 6, 0, 0, 0}, {1, 0, 9, 0, 0, 3, 0},
{7, 9, 0, 0, 0, 0, 1}, {6, 0, 0, 0, 2, 0, 0},
{0, 0, 0, 2, 0, 0, 0}, {0, 3, 0, 0, 0, 0, 3},
{0, 0, 0, 0, 5, 3, 0}};
dijkstra(graph, 0);
}
Sortie :
Vertex Distance Path 1->2 1 1 2 1->3 7 1 3 1->4 6 1 4 1->5 8 1 4 5 1->6 4 1 2 6 1->7 7 1 2 6 7
Python implémentation de l'algorithme de Dijkstra
Pour implémenter l'algorithme de Dijkstra en utilisant python, voici le code :
num_of_vertex = 7
def minimumDistance(distance, visited):
_min = 1e11
min_index = 1e11
for i in range(num_of_vertex):
if not visited[i] and distance[i] & lt; = _min:
_min = distance[i]
min_index = i
return min_index
def printParentNode(parent, i):
if parent[i] == -1:
return
printParentNode(parent, parent[i])
print("{} ".format(i + 1), end = "")
def dijkstra(graph, src):
distance = list()
visited = list()
parent = list()
for i in range(num_of_vertex):
parent.append(-1)
distance.append(1e11)
visited.append(False)
distance[src] = 0
for i in range(num_of_vertex - 1):
U = minimumDistance(distance, visited)
visited[U] = True
for j in range(num_of_vertex):
curr_distance = distance[U] + graph[U][j]
if not visited[j] and graph[U][j] and curr_distance & lt;
distance[j]: parent[j] = U
distance[j] = curr_distance
print("Vertex\t\tDistance\tPath")
for i in range(num_of_vertex):
print("{}->{}\t\t{}\t\t{}
".format(src + 1, i + 1, distance[i], src + 1), end = "")
printParentNode(parent, i)
print("")
graph = [
[0, 1, 7, 6, 0, 0, 0],
[1, 0, 9, 0, 0, 3, 0],
[7, 9, 0, 0, 0, 0, 1],
[6, 0, 0, 0, 2, 0, 0],
[0, 0, 0, 2, 0, 0, 0],
[0, 3, 0, 0, 0, 0, 3],
[0, 0, 0, 0, 5, 3, 0]
]
dijkstra(graph, 0)
Sortie :
Vertex Distance Path 1->1 0 1 1->2 1 1 2 1->3 7 1 3 1->4 6 1 4 1->5 8 1 4 5 1->6 4 1 2 6 1->7 7 1 2 6 7
Nous pouvons voir que l'algorithme calcule la distance la plus courte depuis le nœud source.
Application de l'algorithme de Dijkstra
Le Dijkstra Algo a un large éventail d’utilisations. Parmi ceux-ci, il est largement utilisé dans le domaine des réseaux. Voici quelques exemples d'utilisation réelle de l'algorithme de Dijkstra :
Dijkstra sur la carte Google : Fondamentalement, cet algorithme est l’épine dorsale de la recherche des chemins les plus courts. Comme nous pouvons le voir dans la sortie de l’extrait de code ci-dessus.
Google n'utilise pas le simple algorithme de Dijkstra. Au lieu de cela, il utilise une version modifiée. Lorsque vous sélectionnez une destination, plusieurs chemins sont affichés sur Google Map. Parmi ces chemins, certains chemins sont triés pour l'utilisateur. Ces chemins sélectionnés sont basés sur le « temps ». Ainsi, le « temps » est un coût supplémentaire pour le chemin le plus court.
Dijkstra dans le routage IP : Routage IP est une terminologie de réseautage. Cela signifie comment votre paquet de données est envoyé au récepteur via différents chemins. Ces chemins sont constitués de routeurs, de serveurs, etc. Dans le routage IP, il existe différents types de protocoles.
Ces protocoles aident le routeur à trouver les chemins les plus courts pour envoyer les données. L'un des noms de protocole est « OSPF (Open Shortest Path First) ». OSPF utilise l'algorithme de Dijkstra. Le routeur gère une table de routes. Chaque routeur partage sa table avec les routeurs voisins. Après avoir reçu le tableau mis à jour, ils doivent recalculer tous les chemins. À ce moment-là, le routeur utilise l’algorithme Dijkstra.
Limitation de l'algorithme de Dijkstra
L'algorithme de Dijkstra ne peut pas garantir le chemin le plus court dans le graphe des bords négatifs. L'algorithme de Dijkstra suit ces méthodologies :
- Un chemin le plus court sera emprunté d’un nœud à un autre.
- Une fois le chemin le plus court entre deux nœuds sélectionné, il ne sera plus calculé.
Ici, remarquez deux exemples avec des bords négatifs.
Dans le graphique de gauche, il y a trois sommets. Dijkstra fonctionnera sur le graphique comme suit :
Étape 1) Le sommet de départ « 1 » sera initialisé à zéro. Les autres nœuds auront l'infini.
Étape 2) Marquez le nœud « 1 » comme visité et incluez-le dans le chemin le plus court.
Étape 3) La distance du nœud source 1 aux nœuds « 2 » et « 3 » est fixée à l'infini, car le chemin le plus court reste à calculer. Ainsi, tout chemin qui coûtera moins que l’infini sera ajouté au chemin le plus court (approche gourmande).
Étape 4) Mise à jour de la distance du sommet source ou du nœud source « 1 » à « 2 ». Le poids actuel sera de 5 (5
Étape 5) Maintenant, si nous vérifions les distances les plus courtes depuis le nœud « 1 », nous constatons que 5 est la distance la plus courte pour le bord 1 -> 2. Ainsi, le nœud « 2 » sera marqué comme visité.
De même, le nœud « 3 » sera également marqué comme visité car la distance la plus courte est 3.
Cependant, si nous observons, il existe un chemin 1-3-2 qui ne coûtera que 2. Mais le Dijkstra montre que du nœud « 1 » au nœud « 2 », la distance la plus courte est 5. Ainsi, Dijkstra n'a pas réussi à calculer la distance la plus courte. distance correctement. La raison pour laquelle cela s'est produit est que Dijkstra est un algorithme gourmand. Ainsi, une fois qu'un nœud est marqué comme visité, il ne sera pas reconsidéré, même s'il peut y avoir un chemin plus court disponible. Ce problème se produit uniquement lorsque les arêtes ont des coûts négatifs ou des arêtes de poids négatifs.
Dijkstra ne parvient pas à calculer le chemin le plus court entre deux nœuds dans ce scénario. En conséquence, cet algorithme présente certains inconvénients. Pour résoudre ce problème de bord négatif, un autre algorithme appelé « Algorithme Bellman-Ford » est utilisé. Cet algorithme peut fonctionner avec des bords négatifs.
Complexité de l'algorithme de Dijkstra
L'implémentation ci-dessus utilisait deux boucles « for ». Ces boucles s'exécutent pour le nombre de sommets. La complexité temporelle est donc O(V2). Ici, le terme « 0 » désigne une notation qui donne une hypothèse pour l'algorithme de Dijkstra.
Nous pouvons stocker le graphique en utilisant la « file d’attente prioritaire ». Une file d'attente prioritaire est une structure de données de tas binaire. Ce sera plus efficace qu’une matrice 2D. Un avantage qui aura un coût minimum aura une haute priorité.
La complexité temporelle sera alors O (E log (V)). Ici, E est le nombre d’arêtes et V est le nombre de sommets.
La complexité de l'espace est O(V2), car nous utilisons une matrice de contiguïté (tableau 2D). La complexité de l'espace peut être optimisée à l'aide d'une liste de contiguïté ou d'une structure de données de file d'attente.
