Algorithme de Dijkstra
Dans le graphique, il y a des nœuds et des bords. Les nœuds sont les valeurs et les bords sont le chemin ou les lignes qui créent des liens entre les deux nœuds. Dans Python, nous pouvons implémenter les nœuds et les bords en utilisant le dictionnaire imbriqué. Nous pouvons représenter les nœuds comme une clé et tous les chemins de ce nœud à d'autres nœuds comme une valeur de cette clé particulière.
L'algorithme de Dijkstra est utilisé pour trouver le chemin le plus court entre le nœud source et le nœud cible. L'approche cet algorithme est utilisée appelée approche gourmand. Donc, dans cet article, nous allons comprendre les concepts de l'algorithme de Dijkstra et comment nous pouvons l'implémenter à l'aide de la programmation Python.
L'algorithme de Dijkstra comme nous l'avons dit auparavant, utilise le concept de l'approche gourmande. Nous pouvons comprendre l'approche gourmand dans un terme normal qui trouve la solution optimale des options disponibles.
Étapes d'algorithme
- Nous initialisons d'abord la valeur du nœud source 0 et d'autres valeurs de nœuds adjacents comme infini.
- Insérez le nœud source et la valeur de distance en paire dans le dictionnaire. Par exemple, la paire de valeurs de nœud source sera . Le s représente le nom du nœud et 0 est la valeur de distance. La valeur 0 est parce que nous initialisons la valeur du nœud source 0.
- La boucle continuera jusqu'à ce que le dictionnaire, pas nul (ou pas vide).
- Nous avons attribué n'importe quelle paire du dictionnaire à current_source_node en fonction de la condition suivante:
La valeur de distance du nœud doit être inférieure aux valeurs de distance des nœuds disponibles. Après cela, supprimez-le de la liste du dictionnaire car c'est maintenant courant_source_node.
- Pour chaque Adjacent_link_node au courant_source_node
- Si (Dist [adjacent_link_node]> Valeur de bord de current_source_node au nœud adjacent + dist [current_source_node])
- Dist [adjacent_link_node] = Valeur Edge de current_source_node au nœud adjacent + dist [current_source_node]
- Puis mettez à jour le dictionnaire avec la paire
Étapes d'algorithme de Dijkstra
L'algorithme de Dijkstra est utilisé pour trouver le chemin le plus court entre le nœud source et le nœud cible.
Étape 1: Pour cela, nous devons d'abord initialiser le nœud source comme un 0 et d'autres nœuds comme ∞. Ensuite, nous insérons la paire dans le dictionnaire. Notre première paire sera due au fait que la distance entre la source à la source elle-même est 0 comme indiqué dans le graphique et le tableau ci-dessous.
| Nœud source | Node de destination | Dist du nœud source | Dictionnaire |
|---|---|---|---|
| 0 | 0 | 0 | [0, 0] |
| 0 | 1 | ∞ | |
| 0 | 2 | ∞ | |
| 0 | 3 | ∞ | |
| 0 | 4 | ∞ | |
| 0 | 5 | ∞ |
Étape 2 Dans le dictionnaire, il n'y a qu'une seule paire . Nous prenons donc cela en tant que courant_source_node et détendons le poids des bords de tous les nœuds adjacents du current_source_node (0).
| Node de source actuel | Nœud adjacent | Dist de la source (0) au nœud adjacent | Mettre à jour le poids de l'EGDE ou non |
|---|---|---|---|
| 0 | 1 | Dist [1] = ∞ | dist [1]> dist_between [0 - 1] + dist [0] i.e ∞> 5 + 0 Alors, nous allons mettre à jour la distance. Mise à jour Dist => Dist [1] = 5 et mettre à jour la paire dans le dict |
| 0 | 2 | Dist [2] = ∞ | dist [2]> dist_between [0 - 2] + distance [0] i.e ∞> 1 + 0 Alors, nous allons mettre à jour la distance. Mise à jour Dist => dist [2] = 1 et mettre à jour la paire dans le dict |
| 0 | 3 | Dist [3] = ∞ | dist [3]> dist_between [0 - 3] + dist [0] donc, nous allons mettre à jour la distance. je.e ∞> 4 + 0 mise à jour dist, i.e Dist [3] = 4 et mettre à jour la paire dans le dict |
| Nœud source | Node de destination | Dist du nœud source | Dictionnaire |
|---|---|---|---|
| 0 | 0 | 0 | [1, 5] [2, 1] [3, 4] |
| 0 | 1 | 5 | |
| 0 | 2 | 1 | |
| 0 | 3 | 4 | |
| 0 | 4 | ∞ | |
| 0 | 5 | ∞ |
Étape 3: Maintenant, nous supprimons la paire suivante du dictionnaire pour le courant_source_node. Mais la condition est que nous devons choisir le nœud de valeur de distance minimale. Nous choisissons donc le dictionnaire et attribué en tant que courant_source_node et détend le poids des bords de tous les nœuds adjacents du courant_source_node (2).
| Node de source actuel | Nœud adjacent | Dist de la source (0) au nœud adjacent | Mettre à jour le poids de l'EGDE ou non |
|---|---|---|---|
| 2 | 0 | Distance [0] = 0 | dist [0] < dist_between [ 2 - 0 ] + dist [ 2 ] i.e 0 dist_between [ 2 - 1 ] + dist [ 2 ] i.e 5 > 3 + 1 |
| 2 | 1 | Distance [1] = 5 | Donc, nous allons mettre à jour la distance. Mise à jour dist ==> Dist [1] = 4 et mettez à jour la paire dans le dict Dist [3]> DIST_BETHEWEN [2 - 3] + Dist [2] I.E 4> 2 + 1 |
| 2 | 3 | Distance [3] = 4 | Donc, nous allons mettre à jour la distance. Mise à jour dist => Dist [3] = 3 et mettez à jour la paire dans le dict Dist [4]> DIST_BETWEEN [2 - 4] + Dist [2] I.e ∞> 1 + 1 |
| 2 | 4 | Distance [4] = ∞ | Donc, nous allons mettre à jour la distance. Mise à jour Dist => dist [4] = 2 Mettez à jour la paire dans le dict |
| Nœud source | Node de destination | Dist du nœud source | Dictionnaire |
|---|---|---|---|
| 2 | 0 | 0 | [1, 4] [3, 3] [4, 2] |
| 2 | 1 | 4 | |
| 2 | 2 | 1 | |
| 2 | 3 | 3 | |
| 2 | 4 | 2 | |
| 2 | 5 | ∞ |
Étape 4: Maintenant, nous supprimons la paire suivante du dictionnaire pour choisir Current_Source_Node et détend le poids des bords de tous les nœuds adjacents du courant_source_node (4).
| Node de source actuel | Nœud adjacent | Dist de la source (0) au nœud adjacent | Mettre à jour le poids de l'EGDE ou non |
|---|---|---|---|
| 4 | 1 | Dist [1] = 4 | dist [1] < dist_between [ 4 - 1 ] + dist [ 4 ] i.e 4 < 8 + 2 No weight updation required. |
| 4 | 2 | dist [2] = 1 | dist [2] < dist_between [ 4 - 2 ] + dist [ 4 ] i.e 1 < 1 + 2 No weight updation required. |
| 4 | 3 | dist [3] = 3 | dist [3] < dist_between [ 4 - 3 ] + dist [ 4 ] i.e 3 < 2 + 2 No weight updation required. |
| 4 | 5 | Dist [5] = ∞ | Donc, nous allons mettre à jour la distance. Mise à jour dist => Dist [5] = 5 Mettez à jour la paire dans le dict |
| Nœud source | Node de destination | Dist du nœud source | Dictionnaire |
|---|---|---|---|
| 4 | 0 | 0 | [1, 4] [3, 3] [5, 5] |
| 4 | 1 | 4 | |
| 4 | 2 | 1 | |
| 4 | 3 | 3 | |
| 4 | 4 | 2 | |
| 4 | 5 | 5 |
Étape 5: Nous supprimons la paire suivante du dictionnaire pour choisir Current_Source_Node et détend le poids des bords de tous les nœuds adjacents du courant_source_node (3).
| Node de source actuel | Nœud adjacent | Dist de la source (0) au nœud adjacent | Mettre à jour le poids de l'EGDE ou non |
|---|---|---|---|
| 3 | 0 | dist [0] = 0 | dist [0] < dist_between [ 3 - 0 ] + dist [ 3 ] i.e 0 < 4 + 3 No weight updation required. |
| 3 | 2 | dist [2] = 1 | dist [2] < dist_between [ 3 - 2 ] + dist [ 3 ] i.e 1 < 2 + 3 No weight updation required. |
| 3 | 4 | dist [4] = 2 | Dist [4] < dist_between [ 3 - 4 ] + dist [ 3 ] i.e 2 < 2 + 3 No weight updation required. |
| 3 | 5 | Dist [5] = 5 | Donc, nous allons mettre à jour la distance. Mise à jour Dist =>Dist [5] = 4 Mettez à jour la paire dans le dict |
| Nœud source | Node de destination | Dist du nœud source | Dictionnaire |
|---|---|---|---|
| 3 | 0 | 0 | [1, 4] [5, 4] |
| 3 | 1 | 4 | |
| 3 | 2 | 1 | |
| 3 | 3 | 3 | |
| 3 | 4 | 2 | |
| 3 | 5 | 4 |
Étape 6: Nous supprimons la paire suivante du dictionnaire pour choisir Current_Source_Node et détend le poids des bords de tous les nœuds adjacents du courant_source_node (1).
| Node de source actuel | Nœud adjacent | Dist de la source (0) au nœud adjacent | Mettre à jour le poids de l'EGDE ou non |
|---|---|---|---|
| 1 | 0 | dist [0] = 0 | Distance [0] < distance_between [ 1 - 0 ] + distance [ 1 ] i.e Since 0 < 5 + 4 No weight updation required. |
| 1 | 2 | dist [2] = 1 | dist [2] < dist_between [ 1 - 2 ] + dist [ 1 ] i.e 1 < 3 + 4 No weight updation required. |
| 1 | 4 | dist [4] = 2 | Dist [4] < dist_between [ 1 - 4 ] + dist [ 1 ] i.e 2 < 8 + 4 No weight updation required. |
| Nœud source | Node de destination | Dist du nœud source | Dictionnaire |
|---|---|---|---|
| 1 | 0 | 0 | [5, 4] |
| 1 | 1 | 4 | |
| 1 | 2 | 1 | |
| 1 | 3 | 3 | |
| 1 | 4 | 2 | |
| 1 | 5 | 4 |
Étape 7: Maintenant, nous supprimons la paire suivante du dictionnaire pour choisir Current_Source_Node et détend le poids des bords de tous les nœuds adjacents du courant_source_node (5).
| Node de source actuel | Nœud adjacent | Dist de la source (0) au nœud adjacent | Mettre à jour le poids de l'EGDE ou non |
|---|---|---|---|
| 5 | 3 | dist [3] = 3 | ddist [3] < dist_between [ 5 - 3 ] + dist [ 5 ] i.e 3 < 1 + 4 No weight updation required. |
| 5 | 4 | dist [4] = 2 | Dist [4] < dist_between [ 5 - 4 ] + dist [ 5 ] i.e 2 < 3 + 4 No weight updation required. |
Maintenant, le dictionnaire est nul et aucune paire laisse derrière. Donc, notre algorithme est maintenant arrêté. Et nous avons obtenu tout le chemin le plus court des nœuds source principaux à tous les autres nœuds comme indiqué ci-dessous:
| Nœud source | Node de destination | Dist du nœud source | Dictionnaire |
|---|---|---|---|
| 0 | 0 | 0 | |
| 0 | 1 | 4 | |
| 0 | 2 | 1 | |
| 0 | 3 | 3 | |
| 0 | 4 | 2 | |
| 0 | 5 | 4 |
Code python: Voici la mise en œuvre de l'algorithme ci-dessus.
1 # algorithme de Dijkstra à Python2 à partir des collections Importation par défaut
3
4 classe Node_dist:
5 def __init __ (self, nom, dist):
6 soi.nom = nom
7 Self.dist = dist
8
9 Dijkstraalgorithme de classe:
dix
11 def __init __ (self, node_count):
12 Self.adjacentList = defaultDict (list)
13 soi.node_count = node_count
14
15 def Adjacent_NodeList (Self, Src, Node_dist):
16 Self.AdjacentList [SRC].APPEND (NODE_DIST)
17
18 def dijkstras_shortest_path (self, source_node):
19 # Initialisez les nœuds avec une valeur et une source infinies
20 # nœud avec 0
21 dist = [999999999999] * Self.node_count
22 dist [source_node] = 0
23
24 # Nous créons un dict comme dit dans l'alogrithme avec le
Paire de valeurs de 25 #
26 dict_of_node_dist = source_node: 0
27
28 while dict_of_node_dist:
29
30 # Maintenant, nous allons assaissiner une paire à un
31 # current_source_node mais conditionne cette valeur distante
32 # devrait être la valeur minimale
33 current_source_node = min (dict_of_node_dist,
34 key = lambda k: dict_of_node_dist [k])
35
36 # Après avoir attribué cette paire à la current_source_node,
37 # Supprimer cet élément du dict
38 del dict_of_node_dist [current_source_node]
39
40 pour node_dist en soi.AdjacentList [current_source_node]:
41 AdjacentNode = node_dist.nom
42 source_to_adjacentnode_dist = node_dist.distr
43
44 # Nous faisons ici la relaxation de bord du nœud adjacent
45 Si dist [adjacentnode]> dist [current_source_node] + \
46 source_to_adjacentnode_dist:
47 Dist [AdjacentNode] = dist [current_source_node] + \
48 source_to_adjacentnode_dist
49 DICT_OF_NODE_DIST [AdjacentNode] = Dist [AdjacentNode]
50
51 pour I à portée (soi.node_count):
52 PRINT ("Distance du nœud source (" + str (source_node) + ") => à"
53 "Node de destination (" + str (i) + ") =>" + str (dist [i]))
54
55 def Main ():
56
57 Graphique = Dijkstraalgorithme (6)
58 graphique.Adjacent_Nodelist (0, Node_dist (1, 5))
59 graphique.Adjacent_Nodelist (0, Node_dist (2, 1))
60 graphique.Adjacent_Nodelist (0, Node_dist (3, 4))
61
62 graphique.Adjacent_Nodelist (1, Node_dist (0, 5))
63 graphique.Adjacent_Nodelist (1, Node_dist (2, 3))
64 graphique.Adjacent_Nodelist (1, Node_dist (4, 8))
65
66 graphique.Adjacent_Nodelist (2, Node_dist (0, 1))
67 graphique.Adjacent_Nodelist (2, Node_dist (1, 3))
68 graphique.Adjacent_Nodelist (2, Node_dist (3, 2))
69 graphique.Adjacent_Nodelist (2, Node_dist (4, 1))
70
71 graphique.Adjacent_Nodelist (3, Node_dist (0, 4))
72 graphique.Adjacent_Nodelist (3, Node_dist (2, 2))
73 graphique.Adjacent_Nodelist (3, Node_dist (4, 2))
74 Graphique.Adjacent_Nodelist (3, Node_dist (5, 1))
75
76 graphique.Adjacent_Nodelist (4, Node_dist (1, 8))
77 graphique.Adjacent_Nodelist (4, Node_dist (2, 1))
78 graphique.Adjacent_Nodelist (4, Node_dist (3, 2))
79 graphique.Adjacent_Nodelist (4, Node_dist (5, 3))
80
81 graphique.Adjacent_Nodelist (5, Node_dist (3, 1))
82 graphique.Adjacent_Nodelist (5, Node_dist (4, 3))
83
84 graphique.Dijkstras_shortest_path (0)
85
86
87 Si __name__ == "__main__":
88 Main ()
Ligne 9 à 53: L'explication de cette classe est donnée ci-dessous:
Ligne 9: Nous avons créé une classe le nom dijkstraalgorithme.
Ligne 11 à 16: Nous initialisons la liste adjacent et le node_count. La liste adjacent est un dict que nous avons utilisé pour stocker le nœud et tous leurs nœuds adjacents, comme le nœud 0: . Ce code si vous imprimez, il affichera le résultat comme ci-dessous:
DefaultDict (DefaultDict (
Le résultat ci-dessus montre que nous créons un dict qui a tous les détails d'un nœud particulier et de ses nœuds adjacents.
Ligne 21 à 22: Nous initialisons tous les nœuds avec une valeur d'infini et des nœuds source avec 0 selon notre algorithme.
Ligne 26: Nous initialisons le dict_of_node_dist selon notre algorithme, qui est notre première paire.
Ligne 28 à 50: Nous mettons en œuvre selon les lignes d'algorithme 4 à 8.
Ligne 57 à 83: Nous avons créé un objet de la classe dijkstraalgorithme et passé le nombre de nœuds dans le graphique. Ensuite, nous avons appelé la méthode adjacent_nodelist en utilisant le graphique d'objet pour faire un dict de tous les nœuds avec leurs nœuds adjacents. Le nœud sera la clé et les nœuds adjacents et la distance seront leurs valeurs.
Ligne 83: Nous avons appelé la méthode dijkstras_shortest_path (0) en utilisant le graphique d'objet.
Sortir: L'algorithme de Python Dijkstra.py
- Distance du nœud source (0) => au nœud de destination (0) => 0
- Distance du nœud source (0) => au nœud de destination (1) => 4
- Distance du nœud source (0) => au nœud de destination (2) => 1
- Distance du nœud source (0) => au nœud de destination (3) => 3
- Distance du nœud source (0) => au nœud de destination (4) => 2
- Distance du nœud source (0) => au nœud de destination (5) => 4
Conclusion
Dans cet article, nous avons étudié l'algorithme de Dijkstra étape par étape. Nous avons également étudié l'idée d'approche gourmande. Nous n'incluons pas les détails de l'approche gourmand car nous reviendrons à ce sujet (approche gourmand) plus tard bientôt.
Le code de cet article est disponible sur le lien GitHub:
https: // github.com / shekharpandey89 / dijkstra-s-algorithme