Dijkstra -Algorithmus
In der Grafik gibt es Knoten und Kanten. Die Knoten sind die Werte und die Kanten sind der Pfad oder die Zeilen, die Verbindungen zwischen den beiden Knoten erzeugen. In Python können wir die Knoten und Kanten mit dem verschachtelten Wörterbuch implementieren. Wir können die Knoten als Schlüssel und alle Pfade von diesem Knoten zu anderen Knoten als Wert dieses bestimmten Schlüssels darstellen.
Der Algorithmus von Dijkstra wird verwendet, um den kürzesten Pfad zwischen dem Quellknoten und dem Zielknoten zu finden. Der Ansatz dieser Algorithmus wird als gieriger Ansatz verwendet. In diesem Artikel werden wir also die Konzepte des Algorithmus von Dijkstra verstehen und wie wir ihn mithilfe der Python -Programmierung implementieren können.
Der Algorithmus von Dijkstra, wie wir bereits sagten, verwendet das Konzept des gierigen Ansatzes. Wir können den gierigen Ansatz in einem normalen Begriff verstehen, der die optimale Lösung aus den verfügbaren Optionen findet.
Algorithmusschritte
- Wir initialisieren zuerst den Quellknotenwert 0 und andere benachbarte Knotenwerte als unendlich.
- Fügen Sie den Quellknoten und den Abstandswert als Paar im Wörterbuch ein. Zum Beispiel wird das Quellknotenwertpaar sein . Der S repräsentiert den Knotennamen und 0 ist der Entfernungswert. Der Wert 0 liegt daran, dass wir den Quellknotenwert 0 initialisieren.
- Die Schleife wird bis zum Wörterbuch fortgesetzt, nicht null (oder nicht leer).
- Wir haben jedes Paar aus dem Dictionary basierend auf der folgenden Bedingung zu Current_Source_Node zugewiesen:
Der Knotenentfernungswert sollte unter den verfügbaren Distanzwerten unter den verfügbaren Knoten liegen. Entfernen Sie das danach aus der Wörterbuchliste, da dies jetzt current_source_node ist.
- Für jede adjacent_link_node an die aktuelle_source_node do
- Wenn (dist [adjacent_link_node]> Kantenwert von Current_Source_Node zum benachbarten Knoten+ Dist [current_source_node]))
- dist [adjacent_link_node] = Randwert von current_source_node zum benachbarten Knoten + Dist [current_source_node]
- Aktualisieren Sie dann das Wörterbuch mit Paar
Dijkstra's Algorithmus Schritte
Der Algorithmus von Dijkstra wird verwendet, um den kürzesten Pfad zwischen dem Quellknoten und dem Zielknoten zu finden.
Schritt 1: Dafür müssen wir den Quellknoten zuerst als 0 und andere Knoten als ∞ initialisieren. Dann setzen wir das Paar in das Wörterbuch ein. Unser erstes Paar liegt daran, dass der Abstand von der Quelle zur Quelle selbst 0 beträgt, wie in der folgenden Grafik und Tabelle gezeigt.
| Quellknoten | Zielknoten | Dist vom Quellknoten | Wörterbuch |
|---|---|---|---|
| 0 | 0 | 0 | [0, 0] |
| 0 | 1 | ∞ | |
| 0 | 2 | ∞ | |
| 0 | 3 | ∞ | |
| 0 | 4 | ∞ | |
| 0 | 5 | ∞ |
Schritt 2 Im Wörterbuch gibt es nur ein Paar . Wir nehmen dies also als current_source_node und entspannen das Gewicht der Kanten aller benachbarten Knoten aus dem current_source_node (0).
| Aktueller Quellknoten | Benachbarter Knoten | Dist von Quelle (0) bis benachbarter Knoten | Aktualisieren Sie das Gewicht von Egde oder nicht |
|---|---|---|---|
| 0 | 1 | dist [1] = ∞ | dist [1]> dist_between [0 - 1] + dist [0] i.E ∞> 5 + 0 Also werden wir die Entfernung aktualisieren. Update dist => dist [1] = 5 und aktualisieren Sie das Paar im DICT |
| 0 | 2 | dist [2] = ∞ | dist [2]> dist_bet zwischen [0 - 2] + distanz [0] i.E ∞> 1 + 0 Also werden wir die Entfernung aktualisieren. Update dist => dist [2] = 1 und aktualisieren Sie das Paar im DICT |
| 0 | 3 | dist [3] = ∞ | dist [3]> dist_between [0 - 3] + dist [0] Also werden wir den Abstand aktualisieren. ich.e ∞> 4 + 0 update dist, i.e dist [3] = 4 und aktualisieren Sie das Paar im DICT |
| Quellknoten | Zielknoten | Dist vom Quellknoten | Wörterbuch |
|---|---|---|---|
| 0 | 0 | 0 | [15] [2, 1] [3, 4] |
| 0 | 1 | 5 | |
| 0 | 2 | 1 | |
| 0 | 3 | 4 | |
| 0 | 4 | ∞ | |
| 0 | 5 | ∞ |
Schritt 3: Jetzt entfernen wir das nächste Paar aus dem Wörterbuch für den current_source_node. Die Bedingung ist jedoch, dass wir den minimalen Distanzwertknoten wählen müssen. Wir wählen also das aus dem Wörterbuch und werden als current_source_node zugegeben und entspannen das Gewicht der Kanten aller benachbarten Knoten aus dem current_source_node (2).
| Aktueller Quellknoten | Benachbarter Knoten | Dist von Quelle (0) bis benachbarter Knoten | Aktualisieren Sie das Gewicht von Egde oder nicht |
|---|---|---|---|
| 2 | 0 | Entfernung [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 | Entfernung [1] = 5 | Wir werden also die Distanz aktualisieren. Aktualisieren dist ==> dist [1] = 4 und aktualisieren Sie das Paar im Diktat dist [3]> dist_between [2 - 3] + dist [2] i.E 4> 2 + 1 |
| 2 | 3 | Entfernung [3] = 4 | Wir werden also die Distanz aktualisieren. Aktualisieren dist => dist [3] = 3 und aktualisieren Sie das Paar im Diktat dist [4]> dist_bet zwischen [2 - 4] + dist [2] i.e ∞> 1 + 1 |
| 2 | 4 | Entfernung [4] = ∞ | Wir werden also die Distanz aktualisieren. Update dist => dist [4] = 2 Aktualisieren Sie das Paar im DICT |
| Quellknoten | Zielknoten | Dist vom Quellknoten | Wörterbuch |
|---|---|---|---|
| 2 | 0 | 0 | [1, 4] [3, 3] [4, 2] |
| 2 | 1 | 4 | |
| 2 | 2 | 1 | |
| 2 | 3 | 3 | |
| 2 | 4 | 2 | |
| 2 | 5 | ∞ |
Schritt 4: Nun entfernen wir das nächste Paar aus dem Wörterbuch, um current_source_node zu wählen und das Gewicht der Kanten aller benachbarten Knoten aus dem current_source_node (4) zu entspannen.
| Aktueller Quellknoten | Benachbarter Knoten | Dist von Quelle (0) bis benachbarter Knoten | Aktualisieren Sie das Gewicht von Egde oder nicht |
|---|---|---|---|
| 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] = ∞ | Wir werden also die Distanz aktualisieren. Aktualisieren dist => dist [5] = 5 Aktualisieren Sie das Paar im DICT |
| Quellknoten | Zielknoten | Dist vom Quellknoten | Wörterbuch |
|---|---|---|---|
| 4 | 0 | 0 | [1, 4] [3, 3] [5, 5] |
| 4 | 1 | 4 | |
| 4 | 2 | 1 | |
| 4 | 3 | 3 | |
| 4 | 4 | 2 | |
| 4 | 5 | 5 |
Schritt 5: Wir entfernen das nächste Paar aus dem Wörterbuch, um current_source_node zu wählen und das Gewicht der Kanten aller benachbarten Knoten aus dem current_source_node (3) zu entspannen.
| Aktueller Quellknoten | Benachbarter Knoten | Dist von Quelle (0) bis benachbarter Knoten | Aktualisieren Sie das Gewicht von Egde oder nicht |
|---|---|---|---|
| 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 | Wir werden also die Distanz aktualisieren. Update dist =>dist [5] = 4 Aktualisieren Sie das Paar im DICT |
| Quellknoten | Zielknoten | Dist vom Quellknoten | Wörterbuch |
|---|---|---|---|
| 3 | 0 | 0 | [1, 4] [5, 4] |
| 3 | 1 | 4 | |
| 3 | 2 | 1 | |
| 3 | 3 | 3 | |
| 3 | 4 | 2 | |
| 3 | 5 | 4 |
Schritt 6: Wir entfernen das nächste Paar aus dem Wörterbuch, um current_source_node zu wählen und das Gewicht der Kanten aller benachbarten Knoten aus dem current_source_node (1) zu entspannen.
| Aktueller Quellknoten | Benachbarter Knoten | Dist von Quelle (0) bis benachbarter Knoten | Aktualisieren Sie das Gewicht von Egde oder nicht |
|---|---|---|---|
| 1 | 0 | dist [0] = 0 | Entfernung [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. |
| Quellknoten | Zielknoten | Dist vom Quellknoten | Wörterbuch |
|---|---|---|---|
| 1 | 0 | 0 | [5, 4] |
| 1 | 1 | 4 | |
| 1 | 2 | 1 | |
| 1 | 3 | 3 | |
| 1 | 4 | 2 | |
| 1 | 5 | 4 |
Schritt 7: Jetzt entfernen wir das nächste Paar aus dem Wörterbuch, um current_source_node zu wählen und das Gewicht der Kanten aller benachbarten Knoten aus dem current_source_node (5) zu entspannen (5).
| Aktueller Quellknoten | Benachbarter Knoten | Dist von Quelle (0) bis benachbarter Knoten | Aktualisieren Sie das Gewicht von Egde oder nicht |
|---|---|---|---|
| 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. |
Jetzt ist das Wörterbuch null und kein Paar zurückgelassen. Also ist unser Algorithmus jetzt gestoppt. Und wir haben den kürzesten Weg von den Hauptquellenknoten zu allen anderen Knoten, wie unten gezeigt:
| Quellknoten | Zielknoten | Dist vom Quellknoten | Wörterbuch |
|---|---|---|---|
| 0 | 0 | 0 | |
| 0 | 1 | 4 | |
| 0 | 2 | 1 | |
| 0 | 3 | 3 | |
| 0 | 4 | 2 | |
| 0 | 5 | 4 |
Python -Code: Unten finden Sie die Implementierung des obigen Algorithmus.
1 # Dijkstra -Algorithmus in Python2 Aus den Sammlungen importieren Sie Standarddict
3
4 Klasse node_dist:
5 def __init __ (Selbst, Name, dist):
6 Selbst.Name = Name
7 Selbst.dist = dist
8
9 Klasse Dijkstraalgorithmus:
10
11 def __init __ (self, node_count):
12 Selbst.AdjacentList = StandardDict (Liste)
13 Selbst.node_count = node_count
14
15 Def adjacent_nodelist (self, src, node_dist):
16 Selbst.Adjacentlist [SRC].append (node_dist)
17
18 def dijkstras_shortest_path (self, socal_node):
19 # Initialisieren Sie die Knoten mit unendlicher Wert und Quelle
20 # Knoten mit 0
21 dist = [999999999999] * Selbst.node_count
22 dist [source_node] = 0
23
24 # Wir erstellen ein Diktat wie im Alogrithmus mit dem
25 # Wertpaar
26 dict_of_node_dist = source_node: 0
27
28 während dict_of_node_dist:
29
30 # Jetzt werden wir ein Paar zu a greifen
31 # Current_Source_Node, aber Bedingung des Wertes für den Wert
32 # sollte der Mindestwert sein
33 current_source_node = min (dict_of_node_dist,
34 Key = Lambda K: dict_of_node_dist [k])
35
36 # Nachdem Sie das Paar dem current_source_node zuweisen können,
37 # Löschen Sie diesen Artikel aus dem Diktat
38 del dict_of_node_dist [current_source_node]
39
40 für Node_dist in Self.Adjazentlist [Current_Source_Node]:
41 adjacentnode = node_dist.Name
42 Source_TO_ADJACENTNODE_DIST = NODE_DIST.distanzieren
43
44 # Wir machen hier die Randentspannung des angrenzenden Knotens
45 Wenn 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 für i in Reichweite (Selbst.node_count):
52 print ("Abstand vom Quellknoten ("+str (source_node)+") => to"
53 "Zielknoten (" + str (i) + ") =>" + str (dist [i]))
54
55 def Main ():
56
57 Graph = Dijkstraalgorithmus (6)
58 Diagramm.Adjacent_nodelist (0, node_dist (1, 5))
59 Diagramm.Adjacent_nodelist (0, node_dist (2, 1))
60 Graph.Adjacent_nodelist (0, node_dist (3, 4))
61
62 Diagramm.Adjacent_nodelist (1, node_dist (0, 5))
63 Diagramm.Adjacent_nodelist (1, node_dist (2, 3))
64 Diagramm.Adjacent_nodelist (1, node_dist (4, 8))
65
66 Diagramm.Adjacent_nodelist (2, node_dist (0, 1))
67 Diagramm.Adjacent_nodelist (2, node_dist (1, 3))
68 Diagramm.Adjacent_nodelist (2, node_dist (3, 2))
69 Diagramm.Adjacent_nodelist (2, node_dist (4, 1))
70
71 Graph.Adjacent_nodelist (3, node_dist (0, 4))
72 Diagramm.Adjacent_nodelist (3, node_dist (2, 2))
73 Diagramm.Adjacent_nodelist (3, node_dist (4, 2))
74 Diagramm.Adjacent_nodelist (3, node_dist (5, 1))
75
76 Diagramm.Adjacent_nodelist (4, node_dist (1, 8))
77 Diagramm.Adjacent_nodelist (4, node_dist (2, 1))
78 Diagramm.Adjacent_nodelist (4, node_dist (3, 2))
79 Diagramm.Adjacent_nodelist (4, node_dist (5, 3))
80
81 Diagramm.Adjacent_nodelist (5, node_dist (3, 1))
82 Diagramm.Adjacent_nodelist (5, node_dist (4, 3))
83
84 Diagramm.Dijkstras_shortest_path (0)
85
86
87 Wenn __name__ == "__main__":
88 main ()
Zeile 9 bis 53: Erläuterung dieser Klasse ist unten angegeben:
Zeile 9: Wir haben eine Klasse erstellt, den Namen Dijkstraalgorithmus.
Zeile 11 bis 16: Wir initialisieren die benachbarte Liste und node_count. Die benachbarte Liste ist ein Diktat, mit dem wir den Knoten und alle ihre benachbarten Knoten wie Knoten 0 gespeichert haben: . In diesem Code wird das Ergebnis wie unten angezeigt, wenn Sie drucken, wie unten:
Standarddikt (Standarddikt (
Das obige Ergebnis zeigt, dass wir ein Diktat erstellen, das alle Details eines bestimmten Knotens und seiner angrenzenden Knoten enthält.
Zeile 21 bis 22: Wir initialisieren alle Knoten mit einem Unendlichkeitswert und Quellenknoten mit 0 wie in unserem Algorithmus.
Zeile 26: Wir initialisieren den dict_of_node_dist gemäß unserem Algorithmus, der unser erstes Paar ist.
Zeile 28 bis 50: Wir implementieren nach Algorithmuszeilen 4 bis 8.
Zeile 57 bis 83: Wir haben ein Objekt der Klasse Dijkstraalgorithmus erstellt und die Anzahl der Knoten in der Grafik übergeben. Dann haben wir die Methode adjacent_nodelist verwendet, um das Objektdiagramm zu verwenden. Der Knoten ist der Schlüssel und benachbarte Knoten und Entfernungen sind ihre Werte.
Zeile 83: Wir haben die Methode dijkstras_shortest_path (0) mit dem Objektgraphen bezeichnet.
Ausgang: Python Dijkstra's Algorithmus.py
- Abstand vom Quellknoten (0) => zum Zielknoten (0) => 0
- Abstand vom Quellknoten (0) => zum Zielknoten (1) => 4
- Abstand vom Quellknoten (0) => zum Zielknoten (2) => 1
- Abstand vom Quellknoten (0) => zum Zielknoten (3) => 3
- Abstand vom Quellknoten (0) => zum Zielknoten (4) => 2
- Abstand vom Quellknoten (0) => zum Zielknoten (5) => 4
Abschluss
In diesem Artikel haben wir den Algorithmus von Dijkstra Schritt für Schritt untersucht. Wir haben auch die gierige Ansatzidee studiert. Wir fügen die Details zum gierigen Ansatz nicht hinzu, da wir später bald auf dieses Thema (gieriger Ansatz) zurückkehren werden.
Der Code für diesen Artikel ist unter dem GitHub -Link verfügbar:
https: // github.com/Shekharpandey89/Dijkstra-s-Algorithmus