L'algoritmo di Dijkstra
Nel grafico, ci sono nodi e bordi. I nodi sono i valori e i bordi sono il percorso o le righe che creano collegamenti tra i due nodi. In Python, possiamo implementare i nodi e i bordi usando il dizionario nidificato. Possiamo rappresentare i nodi come chiave e tutti i percorsi da quel nodo ad altri nodi come valore di quella particolare chiave.
L'algoritmo di Dijkstra viene utilizzato per trovare il percorso più breve tra il nodo di origine e il nodo target. L'approccio questo algoritmo è usato chiamato approccio avido. Quindi, in questo articolo, capiremo i concetti dell'algoritmo di Dijkstra e come possiamo implementarlo usando la programmazione di Python.
L'algoritmo di Dijkstra come abbiamo detto prima, sta usando il concetto di avido approccio. Possiamo capire l'approccio avido in un termine normale che trova la soluzione ottimale dalle opzioni disponibili.
Passi di algoritmo
- Per prima cosa inizializziamo il valore del nodo di origine 0 e altri valori di nodi adiacenti come infiniti.
- Inserire il nodo di origine e il valore della distanza come coppia nel dizionario. Ad esempio, la coppia del valore del nodo di origine sarà . La s rappresenta il nome del nodo e 0 è il valore della distanza. Il valore 0 è perché inizializziamo il valore del nodo di origine 0.
- Il cappio continuerà fino al dizionario, non nullo (o non vuoto).
- Abbiamo assegnato qualsiasi coppia dal dizionario a current_source_node in base alla seguente condizione:
Il valore della distanza del nodo dovrebbe essere inferiore ai valori di distanza dei nodi disponibili. Successivamente, rimuovilo dall'elenco dei dizionari perché ora è corrente_source_node.
- Per ciascuno addacent_link_node a current_source_node do
- Se (dist [addacent_link_node]> bordo valore da current_source_node al nodo adiacente+ dist [current_source_node])
- dist [adiacent_link_node] = valore edge da current_source_node al nodo adiacente + dist [current_source_node]
- Quindi aggiorna il dizionario con la coppia
Passaggi dell'algoritmo di Dijkstra
L'algoritmo di Dijkstra viene utilizzato per trovare il percorso più breve tra il nodo di origine e il nodo target.
Passo 1: Per questo, dobbiamo prima inizializzare il nodo di origine come 0 e altri nodi come ∞. Quindi inseriamo la coppia nel dizionario. La nostra prima coppia sarà perché la distanza dalla sorgente alla sorgente stessa è 0 come mostrato nel grafico seguente e nella tabella.
| Nodo di origine | Nodo di destinazione | Dist dal nodo di origine | Dizionario |
|---|---|---|---|
| 0 | 0 | 0 | [0, 0] |
| 0 | 1 | ∞ | |
| 0 | 2 | ∞ | |
| 0 | 3 | ∞ | |
| 0 | 4 | ∞ | |
| 0 | 5 | ∞ |
Passo 2 Nel dizionario c'è solo una coppia . Quindi, prendiamo questo come current_source_node e rilassiamo il peso dei bordi di tutti i nodi adiacenti da current_source_node (0).
| nodo di origine corrente | Nodo adiacente | Dist dal nodo adiacente al nodo adiacente | Aggiornare il peso di egde o no |
|---|---|---|---|
| 0 | 1 | dist [1] = ∞ | dist [1]> dist_between [0 - 1] + dist [0] i.E ∞> 5 + 0 Quindi, aggiorneremo la distanza. Aggiorna dist => dist [1] = 5 e aggiorna la coppia nel DICT |
| 0 | 2 | dist [2] = ∞ | dist [2]> dist_between [0 - 2] + distanza [0] i.E ∞> 1 + 0 Quindi, aggiorneremo la distanza. Aggiorna dist => dist [2] = 1 e aggiorna la coppia nel DICT |
| 0 | 3 | dist [3] = ∞ | dist [3]> dist_between [0 - 3] + dist [0] Quindi, aggiorneremo la distanza. io.E ∞> 4 + 0 Aggiornamento dist, i.e dist [3] = 4 e aggiorna la coppia nel DICT |
| Nodo di origine | Nodo di destinazione | Dist dal nodo di origine | Dizionario |
|---|---|---|---|
| 0 | 0 | 0 | [1, 5] [2, 1] [3, 4] |
| 0 | 1 | 5 | |
| 0 | 2 | 1 | |
| 0 | 3 | 4 | |
| 0 | 4 | ∞ | |
| 0 | 5 | ∞ |
Passaggio 3: Ora, rimuoviamo la coppia successiva dal dizionario per current_source_node. Ma la condizione è che dobbiamo scegliere il nodo del valore della distanza minimo. Quindi, scegliamo il dizionario e assegnato come corrente_source_node e rilassiamo il peso dei bordi di tutti i nodi adiacenti da current_source_node (2).
| nodo di origine corrente | Nodo adiacente | Dist dal nodo adiacente al nodo adiacente | Aggiornare il peso di egde o no |
|---|---|---|---|
| 2 | 0 | distanza [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 | distanza [1] = 5 | Quindi, aggiorneremo la distanza. Aggiornamento dist ==> dist [1] = 4 e aggiorna la coppia nella dist [3]> dist_between [2 - 3] + dist [2] i.E 4> 2 + 1 |
| 2 | 3 | distanza [3] = 4 | Quindi, aggiorneremo la distanza. Aggiornamento dist => dist [3] = 3 e aggiorna la coppia nella dist [4]> dist_between [2 - 4] + dist [2] i.E ∞> 1 + 1 |
| 2 | 4 | distanza [4] = ∞ | Quindi, aggiorneremo la distanza. Aggiorna dist => dist [4] = 2 Aggiorna la coppia nel DICT |
| Nodo di origine | Nodo di destinazione | Dist dal nodo di origine | Dizionario |
|---|---|---|---|
| 2 | 0 | 0 | [1, 4] [3, 3] [4, 2] |
| 2 | 1 | 4 | |
| 2 | 2 | 1 | |
| 2 | 3 | 3 | |
| 2 | 4 | 2 | |
| 2 | 5 | ∞ |
Passaggio 4: Ora, rimuoviamo la coppia successiva dal dizionario per scegliere current_source_node e rilassiamo il peso dei bordi di tutti i nodi adiacenti da current_source_node (4).
| nodo di origine corrente | Nodo adiacente | Dist dal nodo adiacente al nodo adiacente | Aggiornare il peso di egde o no |
|---|---|---|---|
| 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] = ∞ | Quindi, aggiorneremo la distanza. Aggiornamento dist => dist [5] = 5 Aggiorna la coppia nel DICT |
| Nodo di origine | Nodo di destinazione | Dist dal nodo di origine | Dizionario |
|---|---|---|---|
| 4 | 0 | 0 | [1, 4] [3, 3] [5, 5] |
| 4 | 1 | 4 | |
| 4 | 2 | 1 | |
| 4 | 3 | 3 | |
| 4 | 4 | 2 | |
| 4 | 5 | 5 |
Passaggio 5: Rimuoviamo la coppia successiva dal dizionario per scegliere current_source_node e rilassiamo il peso dei bordi di tutti i nodi adiacenti da current_source_node (3).
| nodo di origine corrente | Nodo adiacente | Dist dal nodo adiacente al nodo adiacente | Aggiornare il peso di egde o no |
|---|---|---|---|
| 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 | Quindi, aggiorneremo la distanza. Aggiorna dist =>dist [5] = 4 Aggiorna la coppia nel DICT |
| Nodo di origine | Nodo di destinazione | Dist dal nodo di origine | Dizionario |
|---|---|---|---|
| 3 | 0 | 0 | [1, 4] [5, 4] |
| 3 | 1 | 4 | |
| 3 | 2 | 1 | |
| 3 | 3 | 3 | |
| 3 | 4 | 2 | |
| 3 | 5 | 4 |
Passaggio 6: Rimuoviamo la coppia successiva dal dizionario per scegliere current_source_node e rilassiamo il peso dei bordi di tutti i nodi adiacenti da current_source_node (1).
| nodo di origine corrente | Nodo adiacente | Dist dal nodo adiacente al nodo adiacente | Aggiornare il peso di egde o no |
|---|---|---|---|
| 1 | 0 | dist [0] = 0 | Distanza [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. |
| Nodo di origine | Nodo di destinazione | Dist dal nodo di origine | Dizionario |
|---|---|---|---|
| 1 | 0 | 0 | [5, 4] |
| 1 | 1 | 4 | |
| 1 | 2 | 1 | |
| 1 | 3 | 3 | |
| 1 | 4 | 2 | |
| 1 | 5 | 4 |
Passaggio 7: Ora, rimuoviamo la coppia successiva dal dizionario per scegliere current_source_node e rilassiamo il peso dei bordi di tutti i nodi adiacenti da current_source_node (5).
| nodo di origine corrente | Nodo adiacente | Dist dal nodo adiacente al nodo adiacente | Aggiornare il peso di egde o no |
|---|---|---|---|
| 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. |
Ora, il dizionario è nullo e nessuna coppia lasciata alle spalle. Quindi, il nostro algoritmo è ora fermato. E abbiamo ottenuto tutto il percorso più breve dal / i nodo di sorgente principale a tutti gli altri nodi come mostrato di seguito:
| Nodo di origine | Nodo di destinazione | Dist dal nodo di origine | Dizionario |
|---|---|---|---|
| 0 | 0 | 0 | |
| 0 | 1 | 4 | |
| 0 | 2 | 1 | |
| 0 | 3 | 3 | |
| 0 | 4 | 2 | |
| 0 | 5 | 4 |
Codice Python: Di seguito è riportata l'implementazione dell'algoritmo sopra.
Algoritmo di 1 # Dijkstra in Python2 Dalle raccolte Importa DefaultDict
3
4 class node_dist:
5 def __init __ (self, name, dist):
6 Self.nome = nome
7 Self.dist = dist
8
9 Classe Dijkstraalgoritmo:
10
11 def __init __ (self, node_count):
12 Self.adiacentList = defaultDict (elenco)
13 Self.node_count = node_count
14
15 def addacent_nodelist (self, src, node_dist):
16 Self.adiacente [SRC].append (node_dist)
17
18 def Dijkstras_shortst_path (self, source_node):
19 # Inizializza i nodi con valore infinito e fonte
20 # nodo con 0
21 dist = [99999999999] * self.node_count
22 dist [source_node] = 0
23
24 # Stiamo creando un detto come detto nell'alogritmo con il
25 # coppia di valori
26 dict_of_node_dist = source_node: 0
27
28 While dict_of_node_dist:
29
30 # Ora, stiamo per assumere una coppia a un
31 # Current_source_node ma condiziona quel valore dist
32 # dovrebbe essere il valore minimo
33 current_source_node = min (dict_of_node_dist,
34 chiave = lambda k: dict_of_node_dist [k])
35
36 # dopo l'assegnazione di quella coppia a current_source_node,
37 # Elimina quell'elemento dal DICT
38 DEL DICT_OF_NODE_DIST [Current_Source_Node]
39
40 per node_dist in sé.adiacentlist [current_source_node]:
41 adiacentNode = node_dist.nome
42 Source_to_adJacentNode_dist = node_dist.Dist
43
44 # Stiamo facendo qui il rilassamento del nodo adiacente
45 se dist [addacentNode]> dist [current_source_node] + \
46 source_to_adjacentnode_dist:
47 dist [addacentNode] = dist [current_source_node] + \
48 Source_to_adjacentnode_dist
49 dict_of_node_dist [addacentnode] = dist [addacentNode]
50
51 per i nella gamma (sé.node_count):
52 print ("Distanza dal nodo sorgente ("+str (sorgente_node)+") => a"
53 "Nodo di destinazione (" + str (i) + ") =>" + str (dist [i]))
54
55 def main ():
56
57 grafico = dijkstraalgorithm (6)
58 grafico.Addacent_nodelist (0, node_dist (1, 5))
59 grafico.Addacent_nodelist (0, node_dist (2, 1))
60 grafico.Addacent_nodelist (0, node_dist (3, 4))
61
62 grafico.Addacent_nodelist (1, node_dist (0, 5))
63 grafico.Addacent_nodelist (1, node_dist (2, 3))
64 grafico.Addacent_nodelist (1, node_dist (4, 8))
65
66 grafico.Addacent_nodelist (2, node_dist (0, 1))
67 grafico.Addacent_nodelist (2, node_dist (1, 3))
68 grafico.Addacent_nodelist (2, node_dist (3, 2))
69 grafico.Addacent_nodelist (2, node_dist (4, 1))
70
71 grafico.Addacent_nodelist (3, node_dist (0, 4))
72 grafico.Addacent_nodelist (3, node_dist (2, 2))
73 grafico.Addacent_nodelist (3, node_dist (4, 2))
74 grafico.Addacent_nodelist (3, node_dist (5, 1))
75
76 grafico.Addacent_nodelist (4, node_dist (1, 8))
77 grafico.Addacent_nodelist (4, node_dist (2, 1))
78 grafico.Addacent_nodelist (4, node_dist (3, 2))
79 grafico.Addacent_nodelist (4, node_dist (5, 3))
80
81 grafico.Addacent_nodelist (5, node_dist (3, 1))
82 grafico.Addacent_nodelist (5, node_dist (4, 3))
83
84 grafico.Dijkstras_ShortT_Path (0)
85
86
87 se __name__ == "__main__":
88 main ()
Riga da 9 a 53: Spiegazione di questa classe è riportata di seguito:
Riga 9: Abbiamo creato una classe il nome dijkstraalgorithm.
Riga da 11 a 16: Inizializziamo l'adiacente e node_count. La lista adiacente è un detto che abbiamo usato per memorizzare il nodo e tutti i loro nodi adiacenti, come il nodo 0: . Questo codice se lo stampi mostrerà il risultato come sotto:
DefaultDict (DefaultDict (
Il risultato sopra mostra che stiamo creando un DICT che ha tutti i dettagli di un particolare nodo e dei suoi nodi adiacenti.
Riga 21 a 22: Inizializziamo tutti i nodi con un valore infinito e nodi di origine con 0 secondo il nostro algoritmo.
Riga 26: Inizializziamo il dict_of_node_dist secondo il nostro algoritmo, che è la nostra prima coppia.
Linea da 28 a 50: Implementiamo secondo le linee dell'algoritmo da 4 a 8.
Riga da 57 a 83: Abbiamo creato un oggetto della classe Dijkstraalgoritmo e abbiamo superato il numero di nodi nel grafico. Quindi abbiamo chiamato il metodo adiacente_nodelist usando il grafico degli oggetti per creare un detto di tutti i nodi con i loro nodi adiacenti. Il nodo sarà la chiave e i nodi e la distanza adiacenti saranno i loro valori.
Riga 83: Abbiamo chiamato il metodo Dijkstras_shortst_path (0) usando il grafico degli oggetti.
Produzione: Algoritmo di Python Dijkstra.Py
- Distanza dal nodo di origine (0) => al nodo di destinazione (0) => 0
- Distanza dal nodo di origine (0) => al nodo di destinazione (1) => 4
- Distanza dal nodo di origine (0) => al nodo di destinazione (2) => 1
- Distanza dal nodo di origine (0) => al nodo di destinazione (3) => 3
- Distanza dal nodo di origine (0) => al nodo di destinazione (4) => 2
- Distanza dal nodo di origine (0) => al nodo di destinazione (5) => 4
Conclusione
In questo articolo, abbiamo studiato l'algoritmo di Dijkstra passo dopo passo. Abbiamo anche studiato l'idea di approccio avido. Non includiamo i dettagli sull'approccio avido perché torneremo presto su questo argomento (approccio avido) presto.
Il codice per questo articolo è disponibile sul collegamento GitHub:
https: // github.com/shekharpandey89/dijkstra-s-algoritmo