L'algoritmo di Dijkstra in Python & C++ (Esempio)

Qual è il percorso più breve o la distanza più breve?

Il percorso dal vertice di partenza al vertice di destinazione che ha un costo minimo è detto percorso più breve o distanza più breve. Nella teoria dei grafi, è possibile che esistano più percorsi da una sorgente a una destinazione. Tra questi percorsi, se ne esiste uno che ha un costo minimo, lo definiamo percorso più breve.

In questo contesto, per "costo" si intende il numero di nodi nel percorso o la somma dei costi su ciascun arco. Un percorso può avere uno o più archi. Il collegamento tra due vertici è chiamato "arco". Esistono diversi tipi di algoritmi per la ricerca del percorso più breve, come l'algoritmo di Dijkstra e l'algoritmo di Bellman-Ford.

In questa sezione, analizzeremo l'algoritmo di Dijkstra. Consideriamo il seguente grafo pesato:

Un grafico ponderato non orientato

• Il termine "ponderato" indica il costo per spostarsi da un nodo all'altro. Ad esempio, per spostarsi dal nodo 1 al nodo 2, il costo o peso è 1.
• Il percorso tra il nodo 1 e il nodo 2 è chiamato arco.
• "Non orientato" significa che è possibile spostarsi da un nodo all'altro e tornare al nodo precedente. Quindi, se proviamo a trovare tutti i percorsi dal nodo 1 al nodo 7, saranno:

Tra questi quattro percorsi, possiamo notare che il primo ha un costo di 7. Pertanto, è il percorso più breve in termini di costo.

Percorso più breve

Come funziona l'algoritmo di Dijkstra

L'algoritmo di Dijkstra è in grado di trovare la distanza più breve sia nei grafi pesati diretti che in quelli non diretti. Questo algoritmo è "greedy" perché sceglie sempre il nodo più vicino o più corto rispetto all'origine. Il termine "greedy" significa che, tra una serie di risultati possibili, l'algoritmo sceglierà il migliore.

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 sorgente. Di conseguenza, si comporta come un algoritmo avido.

Nella sezione "esempio" qui sotto, troverete la procedura passo passo. Funziona nel seguente modo:

Passo 1) Inizializza il nodo iniziale con costo 0 e tutti gli altri nodi con costo infinito.
Passo 2) Mantenere un array o una lista per conservare track dei nodi visitati.
Passo 3) Aggiorna il costo del nodo con il costo minimo. Puoi farlo confrontando il costo attuale con il costo del percorso (come mostrato nella sezione degli esempi).
Passo 4) Continuare con il passaggio 3 finché non sono stati visitati tutti i nodi.

Dopo aver completato tutti questi passaggi, troveremo il percorso che costa il minimo dalla fonte alla destinazione.

Differenza tra Dijkstra e BFS, DFS

La principale differenza tra Dijkstra e BFS-DFS è che Dijkstra è un algoritmo di ricerca del percorso più breve, mentre BFS e DFS sono algoritmi di ricerca del percorso più generici. In generale, BFS e DFS non considerano il costo degli archi durante la ricerca del percorso. Pertanto, questi algoritmi non possono garantire il percorso più breve.

Dimostrazione tramite griglia 2D del funzionamento dell'algoritmo BFS.

Algosketch, che mostra la dimostrazione 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.

Vediamo un esempio di grafico:

Qui, BFS trova un percorso al livello 2. BFS attraversa il grafo in ordine di livello. Quindi, procede in questo modo:

Passo 1) Parti dal nodo “1” e visita tutti i nodi adiacenti 2, 3, 4.

Passo 2) Contrassegna i nodi 2, 3 e 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 possiamo vedere, DFS calcola il costo del percorso in base al numero di archi. 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, per quanto riguarda l'algoritmo di Dijkstra, esso seleziona gli archi in base al loro costo. Essendo un algoritmo greedy, sceglierà i percorsi con il 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, i percorsi più brevi vengono calcolati tramite pesi. Non vengono esplorati tutti i percorsi possibili. Illustriamo l'algoritmo di Dijkstra con un esempio. Supponiamo di dover 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 a 0. Assegna “Inf” al resto dei nodi. Significa che non esiste un percorso tra la sorgente e il nodo, oppure che il percorso non è ancora stato visitato.

Passo 2) Quando selezioni il nodo 1, questo verrà contrassegnato come visitato. Quindi aggiorna tutti i nodi adiacenti al nodo 1. 2, 3, 4 sono i nodi adiacenti al nodo 1.

Durante l'aggiornamento di un costo, dobbiamo seguire la procedura seguente:

Possiamo aggiornare il costo di ciascun nodo utilizzando la formula sopra riportata. Ad esempio, ci trovavamo al nodo 1 e dovevamo aggiornare il costo dei nodi adiacenti 2, 3 e 4. Dopo l'aggiornamento, i costi appariranno così:

Passo 3) Per il nodo "2", i vicini sono 6 e 3. Stiamo aggiornando il costo al nodo "6" confrontando infinito (valore corrente) con il costo del nodo 2 più il costo del percorso da 2 a 6. In parole semplici, il nodo "6" avrà un costo pari a 1+3, ovvero 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.

Passo 4) Per il nodo 3, il nodo adiacente è 7. Quindi, confrontando il valore corrente del nodo 7 con il costo del percorso (7+1) ovvero 8, aggiorneremo il costo del nodo 7. Cioè 8. Quindi, troviamo un percorso dal nodo 1 al nodo 7, che è 1→3→7. Il costo è 8.

Passo 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 i passaggi 4 e 5, il risultato sarà il seguente:

Ora, il percorso 1-3-7 ha un 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 di 4. Quindi il percorso 1-2-6-7 avrà un costo di 7.

Poiché 7 < 8, il percorso più breve dal vertice di partenza "1" al vertice di destinazione "7" sarà 1-2-6-7 e il costo è 7. In precedenza era 1-3-7 e il costo era 8. Quindi, il grafo finale sarà il seguente:

Il bordo contrassegnato da una linea nera è il nostro percorso più breve da 1 a 7 e ci costerà 7.

Soprannome Code Algoritmo di Dijkstra

Ecco lo pseudocodice dell'algoritmo di Dijkstra:

Dijkstra(G, S):
  for each vertex V in G
    distance[V] <- Infinity
    previous[V] <- NULL
    if V does not equal S, then,
      (priority queue) Q.push(V)
  distance[S] = 0
  While Q is not empty
    U <- Extract the MIN from Q
    For each unvisited adjacent V of U
      TotalDistance <- distance[U] + edge_cost(U, V)
      if TotalDistance is less than distance[V], then
        distance[V] <- TotalDistance
        previous[V] <- 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] && 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] && graph[U][j] &&
          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 PythonEcco 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] <= _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 < 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 osservare che l'algoritmo calcola la distanza più breve dal nodo sorgente.

Applicazione dell'algoritmo di Dijkstra

L'algoritmo di Dijkstra ha una vasta gamma di applicazioni. Tra queste, è ampiamente utilizzato nel campo delle reti. Ecco alcuni esempi concreti di utilizzo dell'algoritmo di Dijkstra:

Dijkstra in Google Mappe: Questo algoritmo costituisce la base per la ricerca dei percorsi più brevi, come si può notare dall'output del frammento di codice riportato sopra.

Google non utilizza il semplice algoritmo di Dijkstra. Invece, utilizza una versione modificata. Quando selezioni una destinazione, ti mostra più percorsi in Google Mappe. Tra questi percorsi, alcuni vengono ordinati per l'utente. Questi percorsi vengono selezionati in base al "tempo". Quindi, il "tempo" rappresenta un costo di collegamento per il percorso più breve.

Dijkstra nel routing IP: Instradamento IP Il routing IP è un termine tecnico di rete. Descrive come un pacchetto di dati viene inviato al destinatario attraverso diversi percorsi. Questi percorsi sono costituiti da router, server e altre apparecchiature. Nel routing IP esistono diversi tipi di protocolli.

Questi protocolli aiutano il router a trovare i percorsi più brevi per inviare i dati. Uno di questi protocolli è "OSPF (Open Shortest Path First)". OSPF utilizza l'algoritmo di Dijkstra. Il router mantiene una tabella di percorsi. Ogni router condivide la propria tabella con i router vicini. Dopo aver ricevuto la tabella aggiornata, questi devono ricalcolare tutti i percorsi. In questa fase, il router utilizza l'algoritmo di Dijkstra.

Limitazione dell'algoritmo di Dijkstra

L'algoritmo di Dijkstra non può garantire il percorso più breve in un grafo con archi negativi. L'algoritmo di Dijkstra si basa sui seguenti principi:

• 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. L'algoritmo di Dijkstra verrà eseguito sul grafo nel modo seguente:

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 a infinito, poiché il percorso più breve deve ancora essere calcolato. Pertanto, qualsiasi percorso con un costo inferiore a infinito verrà aggiunto al percorso più breve (approccio greedy).

Passo 4) Aggiornamento della distanza dal vertice sorgente "1" al "2". Il peso corrente sarà 5 (5 < infinito). Analogamente, aggiornamento della distanza dal nodo "1" al "3" con peso 3.

Passo 5) Ora, se controlliamo le distanze più brevi dal nodo "1", scopriamo che 5 è la distanza più breve per l'arco 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, esiste un percorso 1-3-2 che costa solo 2. Ma Dijkstra mostra che dal nodo "1" al nodo "2" la distanza più breve è 5. Quindi, Dijkstra non è riuscito a calcolare correttamente la distanza più breve. Il motivo è che Dijkstra è un algoritmo greedy. 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 gli archi hanno costi negativi o pesi negativi.

In questo scenario, l'algoritmo di Dijkstra non riesce a calcolare il percorso più breve tra due nodi. Di conseguenza, presenta alcuni svantaggi. Per risolvere il problema degli archi negativi, si utilizza un altro algoritmo chiamato "algoritmo di Bellman-Ford", che è in grado di gestire anche gli archi 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(V²)In questo contesto, il termine “O” è una notazione che fornisce un'ipotesi per l'algoritmo di Dijkstra.

Possiamo memorizzare il grafo utilizzando una "coda di priorità". Una coda di priorità è una struttura dati heap binaria. Sarà più efficiente di una matrice 2D. Un arco con un costo minimo avrà un'alta priorità. 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(V²), 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.

DOMANDE FREQUENTI