Algoritmul lui Dijkstra în Python & C++ (Exemplu)

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ă un minim este cea mai scurtă cale sau cea mai scurtă distanță. În teoria grafurilor, este posibil să existe mai multe rute de la o sursă la o destinație. Printre aceste rute, dacă există o rută care costă un minim, o numim cea mai scurtă cale.

Aici, „costul” înseamnă numărul de noduri din rută sau suma costurilor pe fiecare muchie. O cale poate avea una sau mai multe muchii. Conexiunea dintre două vârfuri se numește „muchie”. Există diverse tipuri de algoritmi pentru cea mai scurtă cale, cum ar fi algoritmul lui Dijkstra și algoritmul Bellman-Ford.

Aici, discutăm despre algoritmul lui Dijkstra. Să analizăm următorul grafic ponderat:

Un grafic ponderat nedirecționat

• Termenul „ponderat” înseamnă costul mutării de la un nod la altul. De exemplu, la mutarea de la nodul 1 la nodul 2, costul sau ponderea este 1.
• Calea dintre nodul 1 și nodul 2 se numește margine.
• „Nedirecționat” înseamnă că te poți deplasa de la un nod la altul și înapoi la nodul anterior. Așadar, dacă încercăm să găsim toate rutele de la nodul 1 la nodul 7, acestea vor fi:

Dintre aceste patru rute, putem observa că prima rută costă 7. Deci, este cea mai scurtă cale din punct de vedere al costului.

Cea mai scurtă cale

Cum funcționează algoritmul lui Dijkstra

Algoritmul lui Dijkstra poate găsi cea mai scurtă distanță atât în ​​grafurile ponderate, orientate, cât și în cele neorientate. Acest algoritm este lacom deoarece alege întotdeauna cel mai scurt sau cel mai apropiat nod de origine. Termenul „lacom” înseamnă că, dintr-un set de rezultate, algoritmul îl va alege pe cel mai bun dintre ele.

Aici, încercăm să găsim cele mai scurte căi dintre toate celelalte rute. Așadar, algoritmul lui Dijkstra găsește toate cele mai scurte căi dintr-un singur nod sursă. Drept 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 inițial cu cost 0 și restul nodurilor cu cost infinit.
Pas 2) Mențineți o matrice sau o listă de păstrat track dintre nodurile vizitate.
Pas 3) Actualizați costul nodului cu costul minim. Acest lucru se poate face comparând costul curent cu costul căii (demonstrat în secțiunea de exemple).
Pas 4) Continuați pasul 3 până când toate nodurile sunt vizitate.

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 un algoritm de găsire a celei mai scurte căi, în timp ce BFS și DFS sunt algoritmi generali de găsire a căilor. În cazuri generale, BFS și DFS nu iau în considerare costul muchiei atunci când găsesc calea. Prin urmare, acești algoritmi nu pot garanta cea mai scurtă cale.

Demonstrație de grilă 2D a modului în care funcționează BFS

Algosketch, care arată demonstrația 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.

Să vedem un exemplu de grafic:

Aici, BFS găsește o cale în nivelul 2. BFS parcurge graficul în ordinea nivelului. Deci, se deplasează astfel:

Pas 1) Începeți de la nodul „1” și vizitați toate nodurile adiacente 2, 3, 4.

Pas 2) Marcați nodurile 2, 3, 4 ca nivel 1 și vizitați nodurile adiacente. Va continua să exploreze toate nodurile adiacente până când ajunge la nodul 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 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.

Totuși, în termenii algoritmului lui Dijkstra, acesta alege muchiile în funcție de costul lor. Fiind un algoritm greedy, va alege căile cu cost minim.

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, acesta va găsi cele mai scurte căi prin calcularea ponderilor. 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 inițial al nodului la 0. Atribuiți „Informații” către restul nodurilor. Înseamnă că nu există nicio cale între sursă și nod sau că calea nu a fost î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, ne aflam la nodul 1 și trebuia să actualizăm costul nodurilor adiacente 2, 3, 4. După actualizare, costurile vor arăta astfel:

Pas 3) Pentru nodul „2”, vecinii sunt 6 și 3. Actualizăm costul la „6” comparând infinitul (valoarea curentă) cu costul nodului 2 + costul căii de la 2 la 6. Simplu spus, 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.

Pas 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. Acesta este 8. Deci, găsim o cale de la nodul 1 la nodul 7, și este 1→3→7. Costul este 8.

Pas 5) Pentru nodul 4, vom actualiza costul nodului adiacent în mod corespunzător. Așadar, nodul „5” va avea un cost actualizat de 8. După pașii 4 și 5, va arăta astfel:

Acum, calea 1-3-7 are costul de 8 (anterior). Nodul „7” nu era marcat ca vizitat deoarece putem ajunge la nodul „7” din nodul „6”. Calea „1-2-6” avea un cost de 4. Deci, calea 1-2-6-7 va avea costul de 7.

Când 7 < 8, 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.

Pseudo Code Algoritmul lui Dijkstra

Iată pseudocodul pentru algoritmul lui 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++ 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] && 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);
}

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 Python, 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] <= _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)

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 observa că algoritmul calculează cea mai scurtă distanță față de nodul sursă.

Aplicarea algoritmului Dijkstra

Algoritmul lui Dijkstra are o gamă largă de utilizări. Printre acestea, este utilizat pe scară largă în domeniul rețelelor. Iată câteva utilizări practice ale algoritmului lui Dijkstra:

Dijkstra în Google Hărți: Acest algoritm este coloana vertebrală pentru găsirea celor mai scurte căi, după cum putem vedea din fragmentul 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, vă afișează mai multe căi în Google Hărți. Printre aceste căi, unele sunt sortate pentru utilizator. Aceste căi sunt selectate în funcție de „timp”. Deci, „timpul” este un cost de margine pentru cea mai scurtă cale.

Dijkstra în rutarea IP: rutare IP „este o terminologie de rețea. Descrie modul în care pachetul de date este trimis către receptor prin diferite căi. Aceste căi constau în routere, servere și alte echipamente. Î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 protocoalelor este „OSPF (Open Shortest Path First)”. OSPF utilizează algoritmul lui Dijkstra. Routerul menține un tabel de rute. Fiecare router își partajează tabelul cu routerele vecine. După ce primesc tabelul actualizat, acestea trebuie să calculeze din nou toate căile. În acel moment, routerul utilizează algoritmul lui Dijkstra.

Limitarea algoritmului lui Dijkstra

Algoritmul lui Dijkstra nu poate garanta cea mai scurtă cale într-un graf cu muchii negative. Algoritmul lui Dijkstra urmează aceste principii:

• 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, există trei vârfuri. Dijkstra va rula pe graf astfel:

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 în cea mai scurtă cale.

Pas 3) Distanța dintre nodul sursă 1 și nodurile „2” și „3” este setată la infinit, deoarece cea mai scurtă cale urmează să fie calculată. Așadar, orice cale care costă mai puțin decât infinitul va fi adăugată la cea mai scurtă cale (abordare lacomă).

Pas 4) Se actualizează distanța de la vârful sursă „1” la „2”. Ponderea curentă va fi 5 (5 < infinit). În mod similar, se actualizează distanța de la nodul „1” la „3” cu ponderea 3.

Pas 5) Acum, dacă verificăm cele mai scurte distanțe de la nodul „1”, constată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 cea mai scurtă distanță este 3.

Totuși, dacă observăm, există o cale 1-3-2 care va costa doar 2. Însă Dijkstra arată că de la nodul „1” la nodul „2”, cea mai scurtă distanță este 5. Deci, Dijkstra nu a reușit să calculeze corect cea mai scurtă distanță. Motivul este că Dijkstra este un algoritm greedy. Așadar, odată ce un nod este marcat ca vizitat, acesta nu va fi reconsiderat, deși ar putea exista o cale mai scurtă disponibilă. Această problemă apare numai atunci când muchiile au costuri negative sau muchii cu pondere negativă.

Dijkstra nu reușește să calculeze cea mai scurtă cale între două noduri în acest scenariu. Prin urmare, acest algoritm are unele dezavantaje. Pentru a rezolva această problemă a muchiilor negative, se utilizează un alt algoritm numit „Algoritmul Bellman-Ford”. Acel algoritm poate funcționa cu muchii 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(V²)Aici, termenul „O” este o notație care oferă o presupunere pentru algoritmul Dijkstra.

Putem stoca graficul folosind o „coadă de prioritate”. O coadă de prioritate este o structură de date heap binară. Va fi mai eficientă decât o matrice 2D. O muchie cu un cost minim va avea o prioritate ridicată. Atunci complexitatea temporală 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(V²), 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ă.

Întrebări frecvente