Dijkstrin algoritam u Python & C++ (Primjer)

Koji je najkraći put ili najkraća udaljenost?

Put od izvornog vrha do odredišnog vrha koji košta minimalno je najkraći put ili najkraća udaljenost. U teoriji grafova moguće je imati više ruta od izvora do odredišta. Među tim rutama, ako postoji ruta koja košta minimalno, nazivamo je najkraćim putem.

Ovdje „trošak“ znači broj čvorova u ruti ili zbroj troškova na svakom bridu. Put može imati jedan ili više bridova. Veza između dva vrha naziva se „brid“. Postoje različite vrste algoritama za najkraći put, kao što su Dijkstrin algoritam i Bellman-Fordov algoritam.

Ovdje raspravljamo o Dijkstrinom algoritmu. Pogledajmo sljedeći ponderirani graf:

Neusmjereni ponderirani graf

• Pojam „ponderirano“ označava trošak premještanja s jednog čvora na drugi. Na primjer, premještanjem s čvora 1 na čvor 2, trošak ili ponder je 1.
• Put između čvora 1 i čvora 2 naziva se rub.
• „Neusmjereno“ znači da se možete kretati s jednog čvora na drugi i natrag na prethodni čvor. Dakle, ako pokušamo pronaći sve rute od čvora 1 do čvora 7, one će biti:

Među ove četiri rute, možemo vidjeti da prva ruta košta 7. Dakle, to je najkraći put u smislu troškova.

Najkraći put

Kako radi Dijkstrin algoritam

Dijkstrin algoritam može pronaći najkraću udaljenost i u usmjerenim i u neusmjerenim ponderiranim grafovima. Ovaj algoritam je pohlepni jer uvijek bira najkraći ili najbliži čvor iz ishodišta. Pojam "pohlepni" znači da će algoritam između skupa ishoda ili rezultata odabrati najbolji od njih.

Ovdje pokušavamo pronaći najkraće putove među svim ostalim rutama. Dakle, Dijkstrin algoritam pronalazi sve najkraće putove od jednog izvornog čvora. Kao rezultat toga, ponaša se kao pohlepni algoritam.

U odjeljku "primjer" u nastavku vidjet ćete postupni pristup. Funkcionira na sljedeći način:

Korak 1) Inicijalizirajte početni čvor s cijenom 0, a ostale čvorove s beskonačnom cijenom.
Korak 2) Održavati niz ili listu za čuvanje track posjećenih čvorova.
Korak 3) Ažurirajte trošak čvora s minimalnim troškom. To se može učiniti usporedbom trenutnog troška s troškom puta (prikazano u odjeljku s primjerima).
Korak 4) Nastavite korak 3 dok se ne posjete svi čvorovi.

Nakon dovršetka svih ovih koraka pronaći ćemo put koji košta minimalno od izvora do odredišta.

Razlika između Dijkstre i BFS, DFS

Glavna razlika između Dijkstre i BFS-DFS-a je u tome što je Dijkstra algoritam za pronalaženje najkraćeg puta, dok su BFS i DFS opći algoritmi za pronalaženje puta. U općim slučajevima, BFS i DFS ne uzimaju u obzir cijenu ruba prilikom pronalaženja puta. Dakle, ovi algoritmi ne mogu jamčiti najkraći put.

2D mrežna demonstracija rada BFS-a

Algosketch, prikazuje BFS demonstraciju

Ova demonstracija pokazuje da BFS pronalazi samo put. Međutim, ne mari za težinu staze. BFS (Pretraživanje u širinu) pretpostavlja da će putovanje od jednog čvora do drugog koštati samo 1.

Pogledajmo primjer grafa:

Ovdje BFS pronalazi put na razini 2. BFS prelazi graf po razinama. Dakle, putuje ovako:

Korak 1) Počnite od čvora „1“ i posjetite sve susjedne čvorove 2, 3, 4.

Korak 2) Označi čvorove 2, 3, 4 kao razinu 1 i posjeti njihove susjedne čvorove. Nastavit će istraživati ​​sve susjedne čvorove dok ne dođe do odredišnog čvora.

Što se tiče DFS-a, proći će put od 1 do 7 na sljedeći način:

• 1→2→3→7 (Originalni trošak 10, DFS trošak 3)
• 1→2→6→7 (Originalni trošak 7, DFS trošak 3)
• 1→3→7 (Originalni trošak 8, DFS trošak 2)
• 1→4→5→7 (Originalni trošak 13, DFS trošak 3)

Kao što vidimo, DFS izračunava cijenu puta s brojem bridova. DFS radi sljedeće:

• DFS može pronaći put od izvora (početnog vrha) do odredišta.
• Ne može jamčiti je li put otkriven od izvornog čvora do odredišta najkraći put ili nije.

Međutim, u smislu Dijkstrinog algoritma, on bira rubove na temelju njihove cijene. Kao pohlepni algoritam, odabrat će putove s minimalnom cijenom.

Primjer Dijkstrinog algoritma

Dijkstrin algoritam koristi cijenu ili težinu za izračun ukupne cijene puta.

Cilj Dijkstrinog algoritma je minimizirati ovaj ukupni trošak ili težinu. U gore prikazanom primjeru pronalazimo najbolje putove od čvora 1 do čvora 7, zatim izračunavamo sve troškove.

U Dijkstrinom algoritmu, pronaći će se najkraći putevi izračunavanjem težina. Neće se tražiti sve moguće puteve. Demonstrirajmo Dijkstrin algoritam na primjeru. Na primjer, zamoljeni ste da pronađete najkraći put od čvora 1 do 7.

U nastavku su navedeni koraci za ovaj postupak:

Korak 1) Inicijalizirajte početnu cijenu čvora na 0. Dodijelite "Inf" do ostatka čvorova. To znači da ne postoji put između izvora i čvora ili put još nije posjećen.

Korak 2) Kada odaberete čvor 1, bit će označen kao posjećen. Zatim ažurirajte sve susjedne čvorove čvora 1. 2, 3, 4 su susjedni čvorovi čvora 1.

Dok ažuriramo trošak, moramo slijediti postupak u nastavku:

Trošak svakog čvora možemo ažurirati pomoću gornje formule. Na primjer, bili smo na čvoru 1 i trebali smo ažurirati trošak susjednih čvorova 2, 3 i 4. Nakon ažuriranja, troškovi će izgledati ovako:

Korak 3) Za čvor „2“, susjedi su 6 i 3. Ažuriramo trošak na „6“ uspoređujući beskonačnost (trenutnu vrijednost) s troškom čvora 2 + trošak puta od 2 do 6. Jednostavno rečeno, čvor „6“ imat će trošak 1 + 3 ili 4.

Čvor 3 je susjed čvora 2. Međutim, izračunali smo njegov trošak u prethodnom koraku, koji je bio 7. Sada, ako je naš put 1-2-3, čvor 3 će imati trošak 10. Put 1-2- 3 će koštati 10, dok će 1 do 3 koštati 7.

Korak 4) Za čvor 3, susjedni čvor je 7. Dakle, uspoređujući trenutnu vrijednost čvora 7 s cijenom puta (7+1) ili 8, ažurirat ćemo cijenu čvora 7. To je 8. Dakle, pronalazimo put od čvora 1 do čvora 7, a on je 1→3→7. Cijena je 8.

Korak 5) Za čvor 4, ažurirat ćemo cijenu susjednog čvora u skladu s tim. Dakle, čvor "5" imat će ažuriranu cijenu od 8. Nakon koraka 4 i 5, izgledat će ovako:

Sada put 1-3-7 ima cijenu 8 (prije). Čvor "7" nije označen kao posjećen jer do čvora "7" možemo doći iz čvora "6". Put "1-2-6" imao je cijenu 4. Dakle, put 1-2-6-7 imat će cijenu 7.

Kako je 7 < 8, najkraći put od izvornog vrha "1" do odredišnog vrha "7" bit će 1-2-6-7, a cijena je 7. Prije je bila 1-3-7, a cijena je bila 8. Dakle, konačni graf će izgledati ovako:

Rub označen crnom crtom je naš najkraći put od 1 do 7, a koštat će nas 7.

Nadimak Code Dijkstrin algoritam

Evo pseudokoda za Dijkstrin algoritam:

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++ Implementacija Dijkstrinog algoritma

Za implementaciju Dijkstrinog algoritma pomoću C++, evo koda:

#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);
}

Izlaz:

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 Implementacija Dijkstrinog algoritma

Za implementaciju Dijkstrinog algoritma pomoću Python, evo koda:

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)

Izlaz:

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

Možemo vidjeti da algoritam izračunava najkraću udaljenost od izvornog čvora.

Primjena Dijkstra algoritma

Dijkstrin algoritam ima širok raspon primjena. Među njima, široko se koristi u području umrežavanja. Evo nekih primjena Dijkstrinog algoritma u stvarnom životu:

Dijkstra u Google Karte: Ovaj algoritam je osnova za pronalaženje najkraćih putova, kao što možemo vidjeti iz gornjeg isječka koda.

Google ne koristi jednostavni Dijkstrin algoritam. Umjesto toga, koristi modificiranu verziju. Kada odaberete odredište, prikazuje vam više putova u Google Karte. Među tim putovima, neki su sortirani za korisnika. Ti se putovi odabiru na temelju „vremena“. Dakle, „vrijeme“ je cijena ruba za najkraći put.

Dijkstra u IP usmjeravanju: IP usmjeravanje je mrežna terminologija. Opisuje kako se vaš podatkovni paket šalje primatelju putem različitih putova. Ti putovi se sastoje od usmjerivača, poslužitelja i druge opreme. U IP usmjeravanju postoje različite vrste protokola.

Ovi protokoli pomažu usmjerivaču da pronađe najkraće putove za slanje podataka. Jedan od naziva protokola je „OSPF (Open Shortest Path First - Prvo Otvori Najkraći Put)“. OSPF koristi Dijkstrin algoritam. Usmjerivač održava tablicu ruta. Svaki usmjerivač dijeli svoju tablicu sa susjednim usmjerivačima. Nakon što prime ažuriranu tablicu, moraju ponovno izračunati sve putove. U tom trenutku usmjerivač koristi Dijkstrin algoritam.

Ograničenje Dijkstrinog algoritma

Dijkstrin algoritam ne može jamčiti najkraći put u grafu s negativnim bridovima. Dijkstrin algoritam slijedi ove principe:

• Od jednog čvora do drugog ići će jedan najkraći put.
• Jednom kada se odabere najkraći put između dva čvora, neće se ponovno izračunati.

Ovdje primijetite dva primjera s negativnim rubovima.

Na lijevom grafu, Postoje tri vrha. Dijkstra će se izvršavati na grafu na sljedeći način:

Korak 1) Početni vrh "1" bit će inicijaliziran na nulu. Ostali čvorovi će imati beskonačnost.

Korak 2) Označi čvor "1" kao posjećen i uvrsti ga u najkraći put.

Korak 3) Udaljenost izvornog čvora 1 do čvorova „2“ i „3“ postavljena je na beskonačnost, budući da najkraći put tek treba izračunati. Dakle, svaki put koji košta manje od beskonačnosti bit će dodan najkraćem putu (pohlepni pristup).

Korak 4) Ažuriranje udaljenosti od izvornog vrha "1" na "2". Trenutna težina bit će 5 (5 < beskonačno). Slično tome, ažurirajte udaljenost od čvora "1" na "3" s težinom 3.

Korak 5) Ako sada provjerimo najkraće udaljenosti od čvora „1“, otkrit ćemo da je 5 najkraća udaljenost za rub 1→2. Dakle, čvor „2“ bit će označen kao posjećen. Slično tome, čvor „3“ također će biti označen kao posjećen jer je najkraća udaljenost 3.

Međutim, ako promatramo, postoji put 1-3-2 koji će koštati samo 2. Ali Dijkstra pokazuje da je od čvora "1" do čvora "2" najkraća udaljenost 5. Dakle, Dijkstra nije ispravno izračunao najkraću udaljenost. Razlog je taj što je Dijkstra pohlepni algoritam. Dakle, nakon što je čvor označen kao posjećen, neće se ponovno razmatrati, iako bi mogao biti dostupan kraći put. Ovaj problem se javlja samo kada rubovi imaju negativne troškove ili rubove negativne težine.

Dijkstra ne uspijeva izračunati najkraći put između dva čvora u ovom scenariju. Kao rezultat toga, ovaj algoritam ima neke nedostatke. Za rješavanje ovog problema negativnih rubova koristi se drugi algoritam nazvan "Bellman-Fordov algoritam". Taj algoritam može raditi s negativnim rubovima.

Složenost Dijkstrinog algoritma

Gornja implementacija koristila je dvije petlje "za". Ove se petlje pokreću za određeni broj vrhova. Dakle, vremenska složenost je O(V²)Ovdje je izraz „O“ oznaka koja daje pretpostavku za Dijkstrin algoritam.

Graf možemo pohraniti pomoću "reda prioriteta". Red prioriteta je binarna struktura podataka hrpe. Bit će učinkovitija od 2D matrice. Rub s minimalnim troškovima imat će visoki prioritet. Tada će vremenska složenost biti O(E log V). Ovdje je E broj bridova, a V broj vrhova.

Složenost prostora je O(V²), budući da koristimo matricu susjedstva (2D niz). Složenost prostora može se optimizirati korištenjem popisa susjedstva ili strukture podataka reda čekanja.

Pitanja i odgovori