Algoritmo di Dijsktra: C++, Python Esempio di codice
Sara Chen
Qual è il percorso più breve o la distanza più breve?
Un percorso dal vertice di origine al vertice di destinazione che costa un minimo è il percorso più breve o la distanza più breve. Nella teoria dei grafi è possibile avere più percorsi da una sorgente a una destinazione. Tra questi percorsi, se esiste un percorso che costa un importo minimo, possiamo chiamarlo algoritmo del percorso più breve.
Qui “Costo” indica il numero di nodi nel percorso o la somma dei costi su ciascun percorso. Un percorso può avere uno o più bordi. La connessione tra due vertici è chiamata “spigolo”. Esistono vari tipi di algoritmi del percorso più breve, come l'algoritmo di Dijkstra, l'algoritmo di Bellman-Ford, ecc.
Qui discutiamo dell'algoritmo di Dijkstra
Diamo un'occhiata al seguente grafico ponderato:
- Il termine “ponderato” significa spostare i costi da un nodo all’altro. Ad esempio, spostandosi dal nodo 1 al nodo 2, il costo o peso è 1.
- Il percorso tra il nodo 1 e il nodo 2 è chiamato bordo.
- "Non indirizzato" significa che puoi spostare un nodo su un altro e tornare al nodo precedente. Quindi, se proviamo a trovare tutti i percorsi dal nodo 1 al nodo 7, allora sarà:
| Itinerario o percorso | Costo |
|---|---|
| 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 |
Tra questi quattro percorsi, possiamo vedere che il primo percorso ci costerà 7. Quindi è il percorso più breve in termini di costo.
Come funziona l'algoritmo di Dijkstra
L'algoritmo di Dijkstra può trovare la distanza più breve nei grafi pesati sia diretti che non orientati. Questo algoritmo è avido perché sceglie sempre il nodo più corto o più vicino all'origine. Il termine “avido” significa che tra una serie di esiti o risultati, l’algoritmo sceglierà il migliore tra loro.
Qui stiamo cercando di trovare i percorsi più brevi tra tutti gli altri percorsi. Quindi, l'algoritmo di Dijkstra trova tutti i percorsi più brevi da un singolo nodo di destinazione. Di conseguenza, si comporta come a algoritmo avido.
Nella sezione "esempio" di seguito vedrai l'approccio passo passo. Funziona come segue:
Passo 1) Inizializza il nodo iniziale con 0 costi e il resto del nodo come Costo Infinito.
Passo 2) Mantieni un array o un elenco per tenere traccia dei nodi visitati
Passo 3) Aggiorna il costo del nodo con il costo minimo. Può essere fatto confrontando il costo attuale con il costo del percorso. (La dimostrazione è mostrata nella sezione di esempio)
Passo 4) Continuare il passaggio 3 finché non viene visitato tutto il nodo.
Dopo aver completato tutti questi passaggi, troveremo il percorso che costa il minimo dalla fonte alla destinazione.
Differenza tra Dijkstra e BFS, DFS
La differenza principale tra Dijkstra e BFS-DFS è che Dijkstra è l'algoritmo di pathfinding più breve e BFS, DFS è l'algoritmo di pathfinding. In generale, BFS e DFS non considerano il costo durante la ricerca del percorso. Pertanto, questi algoritmi non possono garantire il percorso più breve.
Dimostrazione in griglia 2D di come funziona BFS
Questa dimostrazione indica che BFS trova solo il percorso. Tuttavia, non si preoccupa del peso del percorso. BFS (Ricerca in base all'ampiezza) presuppone che viaggiare da un nodo a un altro nodo costerà solo 1.
Ma vediamo un grafico di esempio:
Qui trova un percorso nel livello 2. BFS attraversa il grafico in ordine di livello. Quindi viaggia come:
Passo 1) Inizia dal nodo “1” e visita tutti i nodi adiacenti 2,3,4
Passo 2) Contrassegna il nodo 2,3,4 come livello 1 e visita i nodi adiacenti. Continuerà ad esplorare tutti i nodi adiacenti fino a raggiungere il nodo di destinazione.
In termini di DFS, attraverserà il percorso da 1 a 7 come segue:
- 1→2→3→7 (Costo originale 10, costo DFS 3)
- 1→2→6→7 (Costo originale 7, costo DFS 3)
- 1→3→7 (Costo originale 8, costo DFS 2)
- 1→4→5→7 (Costo originale 13, costo DFS 3)
Come vediamo, DFS calcola il costo del percorso con il numero di profondità o il numero di bordi.
DFS esegue le seguenti operazioni:
- DFS può trovare un percorso dall'origine (vertice iniziale) alla destinazione.
- Non può garantire se il percorso scoperto dal nodo di origine alla destinazione sia il percorso più breve o meno.
Tuttavia, in termini di algoritmo Dijkstra, sceglierà i bordi in base al loro costo. Come un algoritmo avido, sceglierà il percorso migliore o quello a costo minimo.
Esempio dell'algoritmo di Dijkstra
L'algoritmo di Dijkstra utilizza il costo o il peso per calcolare il costo totale del percorso.
L'obiettivo dell'algoritmo di Dijkstra è ridurre al minimo questo costo o peso totale. Nell'esempio mostrato sopra, troviamo i percorsi migliori dal nodo 1 al nodo 7, quindi calcoliamo tutti i costi.
Nell'algoritmo di Dijkstra, troverà i percorsi più brevi calcolando i pesi. Non cercherà tutti i percorsi possibili. Dimostriamo l'algoritmo di Dijkstra con un esempio. Ad esempio, ti è stato chiesto di trovare il percorso più breve dal nodo 1 al nodo 7.
Per questo processo, i passaggi sono indicati di seguito:
Passo 1) Inizializza il costo del nodo iniziale su 0.
Resto del nodo, assegna “Inf”. Significa che non esiste alcun percorso tra il vertice iniziale (la sorgente) e il nodo, oppure il percorso non è ancora stato visitato.
Passo 2) Quando selezioni il nodo 1, verrà contrassegnato come visitato. Quindi aggiorna tutti i vicini adiacenti del nodo 1. 2,3,4 sono i nodi vicini del nodo 1.
Durante l'aggiornamento di un costo, dobbiamo seguire la procedura seguente:
Possiamo aggiornare il costo di ciascun nodo utilizzando la formula sopra. Ad esempio, eravamo al nodo 1 e dovevamo aggiornare il costo del nodo adiacente 2,3,4.
Dopo l'aggiornamento, il costo o il peso sarà simile a questo:
Passaggio 3) Per il nodo “2”, i vicini sono 6 e 3. Stiamo aggiornando il costo a “6” confrontando l'infinito (valore attuale). Il costo del nodo 2 + costo del percorso da 2 a 6. In parole povere, il nodo “6” avrà il costo di 1+3 o 4.
Il nodo 3 è vicino al nodo 2. Tuttavia, abbiamo calcolato il suo costo nel passaggio precedente, che era 7. Ora, se il nostro percorso è 1-2-3, il nodo 3 avrà un costo pari a 10. Percorso 1-2- 3 costeranno 10, mentre da 1 a 3 costeranno 7.
Passaggio 4) Per il nodo 3, il nodo vicino è 7. Quindi, confrontando il valore attuale del nodo 7 con il costo del percorso (7+1) o 8, aggiorneremo il costo del nodo 7. Cioè 8.
Quindi, troviamo un percorso dal nodo 1 al nodo 7, ed è 1→ 3→ 7. Il costo è 8.
Passaggio 5) Per il nodo 4, aggiorneremo di conseguenza il costo del nodo adiacente. Quindi, il nodo “5” avrà un costo aggiornato pari a 8. Dopo il passaggio 4,5, sarà simile a questo:
Adesso il percorso 1-3-7 ha il costo di 8 (in precedenza). Il nodo “7” non è stato contrassegnato come visitato perché possiamo raggiungere il nodo “7” dal nodo “6”. Il percorso “1-2-6” aveva un costo pari a 4. Quindi il percorso 1-2-6-7 avrà un costo pari a 7.
Poiché 7 < 8, ecco perché il percorso più breve dal vertice di origine “1” al vertice di destinazione “7” sarà 1-2-6-7 e il costo è 7. In precedenza era 1-3-7 e il costo erano le 8.
Quindi, il grafico finale sarà simile a questo:
Il bordo contrassegnato da una linea nera è il nostro percorso più breve da 1 a 7 e ci costerà 7.
Algoritmo di Pseudocodice Dijkstra
Ecco lo pseudo-codice per l'algoritmo di 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++ implementazione dell'algoritmo di Dijkstra
Per implementare l'algoritmo di Dijkstra utilizzando C++, ecco il codice:
#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);
}
Produzione:
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 implementazione dell'algoritmo di Dijkstra
Per implementare l'algoritmo di Dijkstra utilizzando python, ecco il codice:
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)
Produzione:
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
Possiamo vedere che l'algoritmo calcola la distanza più breve dal nodo sorgente.
Applicazione dell'algoritmo di Dijkstra
Il Dijkstra Algo ha una vasta gamma di utilizzi. Tra questi, è ampiamente utilizzato nel campo del networking. Ecco alcuni esempi di utilizzo nella vita reale dell'algoritmo di Dijkstra:
Dijkstra nella mappa di Google: Fondamentalmente, questo algoritmo è la spina dorsale per trovare i percorsi più brevi. Come possiamo vedere dall'output del frammento di codice sopra.
Google non utilizza il semplice algoritmo Dijkstra. Utilizza invece una versione modificata. Quando selezioni una destinazione, ti mostra più percorsi nella mappa di Google. Tra questi percorsi, alcuni percorsi sono smistati per l'utente. Questi percorsi selezionati sono basati sul “tempo”. Quindi, il “tempo” è un costo vantaggio per il percorso più breve.
Dijkstra nel routing IP: Instradamento IP è una terminologia di rete. Significa come il tuo pacchetto di dati viene inviato al ricevitore attraverso percorsi diversi. Questi percorsi sono costituiti da router, server, ecc. Nel routing IP esistono diversi tipi di protocolli.
Questi protocolli aiutano il router a trovare i percorsi più brevi per inviare i dati. Uno dei nomi dei protocolli è "OSPF (Open Shortest Path First)". OSPF utilizza l'algoritmo di Dijkstra. Il router mantiene una tabella di percorsi. Ogni router condivide la sua tabella con i router vicini. Dopo aver ricevuto la tabella aggiornata, devono calcolare di nuovo tutti i percorsi. A quel punto, il router utilizza l'algoritmo di Dijkstra.
Limitazione dell'algoritmo di Dijkstra
L'algoritmo Dijkstra non può garantire il percorso più breve nel grafico del bordo negativo. L'algoritmo di Dijkstra segue queste metodologie:
- Da un nodo all'altro verrà preso il percorso più breve.
- Una volta selezionato il percorso più breve tra due nodi, questo non verrà ricalcolato.
Qui, notate due esempi con bordi negativi.
Nel grafico a sinistra, ci sono tre vertici. Dijkstra eseguirà il grafico come segue:
Passo 1) Il vertice iniziale “1” verrà inizializzato a zero. Gli altri nodi avranno infinito.
Passo 2) Contrassegna il nodo “1” come visitato e includilo nel percorso più breve.
Passo 3) La distanza del nodo sorgente 1 dai nodi “2” e “3” è impostata su infinito, poiché il percorso più breve deve ancora essere calcolato. Pertanto, qualsiasi percorso che costerà meno dell'infinito verrà aggiunto al percorso più breve (approccio goloso).
Passo 4) Aggiornamento della distanza dal vertice di origine o dal nodo di origine da “1” a “2”. Il peso attuale sarà 5 (5
Passo 5) Ora, se controlliamo le distanze più brevi dal nodo “1”, troviamo che 5 è la distanza più breve per il bordo 1–> 2. Quindi, il nodo “2” verrà contrassegnato come visitato.
Allo stesso modo, anche il nodo “3” verrà contrassegnato come visitato poiché la distanza più breve è 3.
Tuttavia, se osserviamo, c'è un percorso 1-3-2 che costerà solo 2. Ma Dijkstra mostra che dal nodo "1" al nodo "2", la distanza più breve è 5. Quindi, Dijkstra non è riuscita a calcolare il percorso più breve distanza correttamente. Il motivo per cui è successo è che Dijkstra è un algoritmo avido. Pertanto, una volta che un nodo viene contrassegnato come visitato, non verrà riconsiderato, anche se potrebbe essere disponibile un percorso più breve. Questo problema si verifica solo quando i bordi hanno costi negativi o bordi con peso negativo
Dijkstra non riesce a calcolare il percorso più breve tra due nodi in questo scenario. Di conseguenza, questo algoritmo presenta alcuni inconvenienti. Per risolvere questo problema del bordo negativo, viene utilizzato un altro algoritmo chiamato “Algoritmo Bellman-Ford”. Questo algoritmo può funzionare con bordi negativi.
Complessità dell'algoritmo di Dijkstra
L'implementazione sopra ha utilizzato due cicli "for". Questi cicli vengono eseguiti per il numero di vertici. Quindi, la complessità temporale è O(V2). Qui, il termine “0” indica una notazione che fornisce un presupposto per l’algoritmo di Dijkstra.
Possiamo memorizzare il grafico utilizzando la “Coda prioritaria”. Una coda con priorità è una struttura di dati heap binaria. Sarà più efficiente di una matrice 2D. Un vantaggio che avrà un costo minimo avrà una priorità alta.
Quindi la complessità temporale sarà O(E log(V)). Dove E è il numero di spigoli e V è il numero di vertici.
La complessità dello spazio è O(V2), poiché stiamo utilizzando una matrice di adiacenza (matrice 2D). La complessità dello spazio può essere ottimizzata utilizzando una lista di adiacenza o una struttura dati di coda.
