Algoritmul lui Dijsktra: C++, Python Exemplu de cod
Sarah Chen
Care este cea mai scurtă cale sau cea mai scurtă distanță?
O cale de la vârful sursă la vârful destinație care costă minim este cea mai scurtă cale sau cea mai scurtă distanță. În teoria graficelor, este posibil să existe mai multe rute de la o sursă la o destinație. Între aceste rute, dacă există o rută care costă o sumă minimă, o putem numi algoritmul cu cea mai scurtă cale.
Aici „Cost” înseamnă numărul de noduri din rută sau suma costurilor pe fiecare cale. O cale poate avea una sau mai multe margini. Legătura dintre două vârfuri se numește „margine”. Există diferite tipuri de algoritmi de calea cea mai scurtă, cum ar fi algoritmul lui Dijkstra, algoritmul Bellman-Ford etc.
Aici, discutăm despre algoritmul lui Dijkstra
Să ne uităm la următorul grafic ponderat:
- Termenul „ponderat” înseamnă mutarea costurilor de la un nod la altul. De exemplu, trecând de la nodul 1 la nodul 2, costul sau greutatea este 1.
- Calea dintre nodul 1 la nodul 2 se numește margine.
- „Nedirecționat” înseamnă că puteți muta un nod în altul și înapoi la nodul anterior. Deci, dacă încercăm să găsim toate rutele de la nodul 1 la nodul 7, atunci va fi:
| Traseu sau Calea | Costat |
|---|---|
| 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 |
Dintre aceste patru trasee, putem observa că primul traseu ne va costa 7. Deci, este calea cea mai scurtă din punct de vedere al costului.
Cum funcționează algoritmul lui Dijkstra
Algoritmul Dijkstra poate găsi cea mai scurtă distanță atât în graficele ponderate direcționate cât și nedirecționate. Acest algoritm este lacom deoarece alege întotdeauna cel mai scurt sau cel mai apropiat nod de la origine. Termenul „lacom” înseamnă că dintr-un set de rezultate sau rezultate, algoritmul va alege cel mai bun dintre ele.
Aici, încercăm să găsim cele mai scurte căi dintre toate celelalte rute. Deci, algoritmul lui Dijkstra găsește toate cele mai scurte căi de la un singur nod de destinație. Ca urmare, se comportă ca un algoritm lacom.
În secțiunea „exemplu” de mai jos, veți vedea abordarea pas cu pas. Funcționează după cum urmează:
Pas 1) Inițializați nodul de pornire cu 0 costuri și restul nodului ca Infinity Cost.
Pas 2) Mențineți o matrice sau o listă pentru a ține evidența nodurilor vizitate
Pas 3) Actualizați costul nodului cu costul minim. Se poate face comparând costul curent cu costul căii. (Demonstrația este prezentată în secțiunea cu exemple)
Pas 4) Continuați pasul 3 până când tot nodul este vizitat.
După parcurgerea tuturor acestor pași, vom găsi calea care costă minim de la sursă la destinație.
Diferența dintre Dijkstra și BFS, DFS
Principala diferență dintre Dijkstra și BFS-DFS este că Dijkstra este cel mai scurt algoritm de căutare a căii, iar BFS, DFS este algoritmul de găsire a căii. În cazuri generale, BFS și DFS nu iau în considerare costul atunci când găsesc calea. Deci, acești algoritmi nu pot garanta calea cea mai scurtă.
Demonstrație grilă 2D a modului în care funcționează BFS
Această demonstrație indică faptul că BFS găsește doar calea. Cu toate acestea, nu îi pasă de greutatea căii. BFS (Lățime-Prima căutare) presupune că călătoria de la un nod la altul va costa doar 1.
Dar să vedem un exemplu de grafic:
Aici, găsește o cale la nivelul 2. BFS traversează Graficul în ordinea nivelului. Deci, călătorește astfel:
Pas 1) Începeți de la nodul „1” și vizitați toate nodurile adiacente 2,3,4
Pas 2) Marcați nodul 2,3,4 ca nivelul 1 și vizitați nodurile adiacente. Va continua să exploreze toate nodurile adiacente până când ajunge la nodul de destinație.
În ceea ce privește DFS, acesta va parcurge calea de la 1 la 7 astfel:
- 1→2→3→7 (costul original 10, costul DFS 3)
- 1→2→6→7 (costul original 7, costul DFS 3)
- 1→3→7 (costul original 8, costul DFS 2)
- 1→4→5→7 (costul original 13, costul DFS 3)
După cum vedem, DFS își calculează costul căii cu numărul de adâncime sau numărul de muchii.
DFS face următoarele:
- DFS poate găsi o cale de la sursă (vârful de pornire) la destinație.
- Nu poate garanta dacă calea descoperită de la nodul sursă la destinație este cea mai scurtă cale sau nu.
Cu toate acestea, în ceea ce privește algoritmul Dijkstra, acesta va alege marginile în funcție de costul acestora. Ca algoritm lacom, va alege cele mai bune sau minime căi de cost.
Exemplu de algoritm al lui Dijkstra
Algoritmul lui Dijkstra utilizează costul sau greutatea pentru a calcula costul total al căii.
Ținta algoritmului Dijkstra este de a minimiza acest cost sau greutate totală. În exemplul prezentat mai sus, găsim cele mai bune căi de la nodul 1 la nodul 7, apoi calculăm toate costurile.
În algoritmul lui Dijkstra, va găsi cele mai scurte căi prin calcularea greutăților. Nu va căuta toate căile posibile. Să demonstrăm algoritmul lui Dijkstra cu un exemplu. De exemplu, vi s-a cerut să găsiți cea mai scurtă cale de la nodul 1 la 7.
Pentru acest proces, pașii sunt dați mai jos:
Pas 1) Inițializați costul nodului de pornire la 0.
Restul nodului, atribuiți „Inf”. Înseamnă că nu există nicio cale între vârful de pornire (sursă) și nod, sau calea nu este încă vizitată.
Pas 2) Când selectați nodul 1, acesta va fi marcat ca vizitat. Apoi actualizați toți vecinii adiacenți ai nodului 1. 2,3,4 sunt nodurile vecine ale nodului 1.
În timpul actualizării unui cost, trebuie să urmăm procedura de mai jos:
Putem actualiza costul fiecărui nod folosind formula de mai sus. De exemplu, eram la nodul 1 și trebuia să actualizăm costul nodului său adiacent 2,3,4.
După actualizare, costul sau greutatea va arăta astfel:
Pasul 3) Pentru nodul „2”, vecinii sunt 6 și 3. Actualizăm costul la „6” comparând infinitul (valoarea curentă). Costul nodului 2 + costul căii de la 2 la 6. Spunând simplu, nodul „6” va avea costul de 1+3 sau 4.
Nodul 3 este vecin cu nodul 2. Cu toate acestea, am calculat costul acestuia în pasul anterior, care a fost 7. Acum, dacă calea noastră este 1-2-3, nodul 3 va avea un cost de 10. Calea 1-2- 3 va costa 10, în timp ce 1 până la 3 va costa 7.
Pasul 4) Pentru nodul 3, nodul vecin este 7. Deci, comparând valoarea curentă a nodului 7 cu costul căii (7+1) sau 8, vom actualiza costul nodului 7. Adică 8.
Deci, găsim o cale de la nodul 1 la nodul 7 și este 1 → 3 → 7. Costul este 8.
Pasul 5) Pentru nodul 4, vom actualiza în consecință costul nodului adiacent. Deci, nodul „5” va avea un cost actualizat de 8. După pasul 4,5, va arăta astfel:
Acum, calea 1-3-7 are costul 8 (anterior). Nodul „7” nu a fost marcat ca vizitat deoarece putem ajunge la nodul „7” de la nodul „6”. Calea „1-2-6” a avut un cost de 4. Deci calea 1-2-6-7 va avea costul de 7.
Ca 7 < 8, de aceea cea mai scurtă cale de la vârful sursă „1” la vârful destinație „7” va fi 1-2-6-7, iar costul este 7. Anterior era 1-3-7, iar costul era 8.
Deci, graficul final va arăta astfel:
Marginea marcată cu o linie neagră este calea noastră cea mai scurtă de la 1 la 7 și ne va costa 7.
Algoritmul lui Dijkstra cu pseudocod
Iată pseudo-codul pentru algoritmul lui 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++ implementarea algoritmului lui Dijkstra
Pentru a implementa algoritmul lui Dijkstra folosind C++, iată codul:
#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);
}
ieșire:
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 implementarea algoritmului lui Dijkstra
Pentru a implementa algoritmul lui Dijkstra folosind piton, iată codul:
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)
ieșire:
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
Putem vedea că algoritmul calculează cea mai scurtă distanță de la nodul sursă.
Aplicarea algoritmului Dijkstra
Dijkstra Algo are un set mare de utilizări. Printre acestea, este utilizat pe scară largă, în domeniul networking-ului. Iată câteva dintre utilizările din viața reală a algoritmului Dijkstra:
Dijkstra pe harta Google: Practic, acest algoritm este coloana vertebrală pentru găsirea celor mai scurte căi. După cum putem vedea din rezultatul fragmentului de cod de mai sus.
Google nu folosește algoritmul simplu Dijkstra. În schimb, folosește o versiune modificată. Când selectați o destinație, aceasta vă arată mai multe căi pe Google Map. Printre aceste căi, unele căi sunt sortate pentru utilizator. Aceste căi selectate se bazează pe „timp”. Deci, „timpul” este un cost marginal pentru calea cea mai scurtă.
Dijkstra în rutarea IP: rutare IP este o terminologie de rețea. Înseamnă modul în care pachetul de date este trimis către receptor prin diferite căi. Aceste căi constau din routere, servere etc. În rutarea IP, există diferite tipuri de protocoale.
Aceste protocoale ajută routerul să găsească cele mai scurte căi pentru a trimite datele. Unul dintre numele protocolului este „OSPF (Open Shortest Path First)”. OSPF folosește algoritmul dijkstra. Routerul menține un tabel de rute. Fiecare router își împarte tabelul cu routerele vecine. După ce primesc tabelul actualizat, trebuie să calculeze din nou toate căile. La acel moment, routerul folosește algoritmul Dijkstra.
Limitarea algoritmului lui Dijkstra
Algoritmul Dijkstra nu poate garanta calea cea mai scurtă din graficul marginii negative. Algoritmul Dijkstra urmează aceste metodologii:
- O cale cea mai scurtă va fi luată de la un nod la altul.
- Odată selectată calea cea mai scurtă între două noduri, aceasta nu va fi calculată din nou.
Aici, observați două exemple cu margini negative.
În graficul din stânga, sunt trei vârfuri. Dijkstra va rula pe grafic după cum urmează:
Pas 1) Vârful de pornire „1” va fi inițializat la zero. Celelalte noduri vor avea infinit.
Pas 2) Marcați Nodul „1” ca vizitat și includeți-l pe calea cea mai scurtă.
Pas 3) Distanța dintre nodul sursă 1 și nodurile „2” și „3” este setată la infinit, deoarece calea cea mai scurtă trebuie încă calculată. Deci, orice cale care va costa mai puțin decât infinitul va fi adăugată la cea mai scurtă cale (abordare greedy).
Pas 4) Actualizarea distanței de la vârful sursă sau nodul sursă „1” la „2”. Greutatea curentă va fi 5 (5
Pas 5) Acum, dacă verificăm cele mai scurte distanțe de la nodul „1”, aflăm că 5 este cea mai scurtă distanță pentru muchia 1–> 2. Deci, nodul „2” va fi marcat ca vizitat.
În mod similar, nodul „3” va fi de asemenea marcat ca vizitat, deoarece distanța cea mai scurtă este 3.
Cu toate acestea, dacă observăm, există o cale 1-3-2 care va costa doar 2. Dar Dijkstra arată că de la nodul „1” la nodul „2”, cea mai scurtă distanță este 5. Deci, Dijkstra nu a reușit să calculeze cea mai scurtă distanță. distanta corect. Motivul pentru care s-a întâmplat este că, Dijkstra este un algoritm lacom. Deci, odată ce un nod este marcat ca vizitat, nu va fi reconsiderat, deși ar putea fi disponibilă o cale mai scurtă. Această problemă apare numai atunci când marginile au costuri negative sau margini de greutate negative
Dijkstra nu reușește să calculeze cea mai scurtă cale între două noduri în acest scenariu. Drept urmare, acest algoritm are unele dezavantaje. Pentru a rezolva această problemă a marginii negative, se folosește un alt algoritm numit „Algoritmul Bellman-Ford”. Acest algoritm poate funcționa cu margini negative.
Complexitatea algoritmului lui Dijkstra
Implementarea de mai sus a folosit două bucle „for”. Aceste bucle rulează pentru numărul de vârfuri. Deci, complexitatea timpului este O(V2). Aici, termenul „0” înseamnă o notație care oferă o presupunere pentru algoritmul Dijkstra.
Putem stoca graficul folosind „Coada de prioritate”. O coadă prioritară este o structură de date heap binară. Va fi mai eficient decât o matrice 2D. Un avantaj care va avea un cost minim va avea o prioritate mare.
Atunci complexitatea timpului va fi O(E log(V)). Aici, E este numărul de muchii, iar V este numărul de vârfuri.
Complexitatea spațiului este O(V2), deoarece folosim o matrice de adiacență (Matrice 2D). Complexitatea spațiului poate fi optimizată folosind o listă de adiacență sau o structură de date în coadă.
