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 c’è un percorso che costa un importo minimo, possiamo chiamarlo l’algoritmo del percorso più breve.
Qui “Costo” indica il numero di nodi nel percorso o la somma dei costi su ciascun percorso. Un tracciato può avere uno o più spigoli. La connessione tra due vertici è chiamata “bordo”. Esistono vari tipi di algoritmi di 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, passando dal nodo 1 al nodo 2, il costo o il peso è 1.
- Il percorso tra il nodo 1 e il nodo 2 è chiamato edge.
- “Non diretto” significa che è possibile spostare un nodo su un altro e tornare al nodo precedente. Quindi, se proviamo a trovare tutte le route dal nodo 1 al nodo 7, allora sarà:
| Percorso 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 costi.
How Dijkstra’s Algorithm Works
Dijkstra algorithm can find the shortest distance in both directed and undirected weighted graphs. This Algorithm is greedy because it always chooses the shortest or closest node from the origin. The term “greedy” means that among a set of outcomes or results, the Algorithm will choose the best of them.
Here, we are trying to find the shortest paths among all other routes. So, Dijkstra’s Algorithm finds all the shortest paths from a single destination node. As a result, it behaves like a greedy algorithm.
In the “example” section below, you’ll see the step-by-step approach. It works as follows:
Step 1) Initialize the starting node with 0 costs and the rest of the node as Infinity Cost.
Step 2) Maintain an array or list to keep track of the visited nodes
Step 3) Update the node cost with the minimum cost. It can be done by comparing the current cost with the path cost. (Demonstration is shown in the example section)
Step 4) Continue step 3 until all the node is visited.
Dopo aver completato tutti questi passaggi, troveremo il percorso che costa un minimo dall’origine alla destinazione.
Differenza tra Dijkstra e BFS, DFS
La principale differenza tra Dijkstra e BFS-DFS è che Dijkstra è l’algoritmo di pathfinding più breve e BFS, DFS è l’algoritmo di pathfinding. In casi generali, BFS e DFS non considerano il costo mentre trovano il percorso. Quindi, questi algoritmi non possono garantire il percorso più breve.
Dimostrazione della griglia 2D di come funziona BFS
Questa dimostrazione indica che BFS trova solo il percorso. Tuttavia, non si preoccupa del peso del percorso. BFS (Breadth-First Search) presuppone che viaggiare da un nodo a un altro nodo costerà solo 1.
Ma vediamo un esempio di grafico:
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 loro 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 il seguente:
- 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 spigoli.
DFS esegue le operazioni seguenti:
- DFS può trovare un percorso dall’origine (vertice iniziale) alla destinazione.
- Non può garantire se il percorso individuato dal nodo di origine alla destinazione sia il percorso più breve o meno.
However, in terms of the Dijkstra Algorithm, it will choose edges based on their cost. As a greedy algorithm, it will pick the best or minimum cost paths.
Example of Dijkstra’s Algorithm
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) Inizializzare il costo del nodo iniziale su 0.
Resto del nodo, assegna “Inf”. Significa che non esiste alcun percorso tra il vertice iniziale (l’origine) e il nodo, oppure il percorso non è ancora visitato.
Passo 2) Quando si seleziona il nodo 1, verrà contrassegnato come visitato. Quindi aggiornare 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 al seguente:
Passo 3) Per il nodo “2”, i vicini sono 6 e 3. Stiamo aggiornando il costo a “6” confrontando l’infinito (valore corrente). Il costo del nodo 2 + costo del percorso da 2 a 6. Semplicemente dicendo, il nodo “6” avrà il costo di 1 + 3 o 4.
Il nodo 3 è un vicino del 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 di 10. Il percorso 1-2-3 costerà 10, mentre da 1 a 3 costerà 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) o 8, aggiorneremo il costo del nodo 7. Questo è 8.
Quindi, troviamo un percorso dal nodo 1 al nodo 7, ed è 1→ 3→ 7. Il costo è di 8.
Passo 5) Per il nodo 4, aggiorneremo di conseguenza il costo del nodo adiacente. Quindi, il nodo “5” avrà un costo aggiornato di 8. Dopo il passaggio 4,5, sarà simile a questo:
Ora, 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 di 4. Quindi il percorso 1-2-6-7 avrà il costo di 7.
Come 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 era 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.
Pseudo codice algoritmo di 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
Implementazione C++ 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);
}
Prodotto:
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
Implementazione Python Algoritmo di Dijkstra
Per implementare l’algoritmo di Dijkstra usando 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)
Prodotto:
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 di origine.
Applicazione dell’algoritmo di Dijkstra
Il Dijkstra Algo ha una vasta gamma di usi. Tra questi, è ampiamente utilizzato, nel campo del networking. Ecco alcuni degli usi reali 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 dello snippet di codice sopra.
Google non utilizza il semplice algoritmo Dijkstra. Invece, utilizza una versione modificata. Quando selezioni una destinazione, ti mostra più percorsi in Google Map. Tra questi percorsi, alcuni percorsi sono ordinati per l’utente. Questi percorsi selezionati si basano sul “tempo”. Quindi, il “tempo” è un costo marginale per il percorso più breve.
Dijkstra nel routing IP: Il routing IP è una terminologia di rete. Significa come il tuo pacchetto di dati viene inviato al destinatario tramite percorsi diversi. Questi percorsi sono costituiti da router, server, ecc. Nel routing IP, ci sono diversi tipi di protocolli.
Questi protocolli aiutano il router a trovare i percorsi più brevi per inviare i dati. Uno dei nomi del protocollo è “OSPF (Open Shortest Path First)”. OSPF utilizza l’algoritmo dijkstra. Il router mantiene una tabella di percorsi. Ogni router condivide la propria tabella con i router vicini. Dopo aver ricevuto la tabella aggiornata, devono calcolare nuovamente tutti i percorsi. A quel tempo, il router utilizza l’algoritmo Dijkstra.
Limitazione dell’algoritmo di Dijkstra
L’algoritmo di Dijkstra non può garantire il percorso più breve nel grafico del bordo negativo. L’algoritmo Dijkstra segue queste metodologie:
- Un percorso più breve verrà portato da un nodo all’altro.
- Una volta selezionato il percorso più breve tra due nodi, non verrà più calcolato.
Qui, nota due esempi con bordi negativi.
Nel grafico di sinistra, ci sono tre vertici. Dijkstra verrà eseguito sul 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. Quindi, qualsiasi percorso che costerà meno dell’infinito verrà aggiunto al percorso più breve (approccio avido).
Passo 4) Aggiornamento della distanza dal vertice di origine o dal nodo di origine “1” a “2”. Il peso attuale sarà 5 (5<infinità). Allo stesso modo, aggiorna la distanza dal nodo “1” a “3” con il peso di 3.
Passo 5) Ora, se controlliamo le distanze più brevi dal nodo “1”, scopriamo che 5 è la distanza più breve per il bordo 1-> 2. Quindi, il nodo “2” sarà contrassegnato come visitato.
Allo stesso modo, anche il nodo “3” sarà contrassegnato come visitato poiché la distanza più breve è 3.
Tuttavia, se osserviamo, c’è un percorso 1-3-2 che costerà solo 2. Ma il 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. La ragione per cui è successo è che, Dijkstra è un algoritmo avido. Quindi, una volta che un nodo è contrassegnato come visitato, non verrà riconsiderato, anche se potrebbe esserci un percorso più breve disponibile. Questo problema si verifica solo quando i bordi hanno costi negativi o bordi di peso negativi
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 di bordo negativo, viene utilizzato un altro algoritmo chiamato “Bellman-Ford Algorithm”. Quell’algoritmo può funzionare con bordi negativi.
Complessità dell’algoritmo di Dijkstra
L’implementazione di cui sopra utilizzava due loop “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’ipotesi per l’algoritmo di Dijkstra.
Possiamo memorizzare il grafico utilizzando la “Coda di priorità”. Una coda di priorità è una struttura di dati heap binaria. Sarà più efficiente di una matrice 2D. Un edge che avrà un costo minimo avrà un’alta priorità.
Quindi la complessità temporale sarà O(E log(V)). Qui, E è il numero di spigoli e V è il numero di vertici.
La complessità dello spazio è O(V2), poiché stiamo usando una matrice di adiacenza (matrice 2D). La complessità dello spazio può essere ottimizzata utilizzando un elenco di adiacenza o una struttura di dati in coda.
fonte: https://www.guru99.com/
