Dijsktra algoritmusa: C++, Python Kódpélda

Mi a legrövidebb út vagy legrövidebb távolság?

A forráscsúcstól a célcsúcsig vezető út, amely minimális költséggel jár, a legrövidebb út vagy a legrövidebb távolság. A gráfelméletben több útvonal is lehetséges a forrástól a célállomásig. Ezen útvonalak között, ha van olyan útvonal, amely minimális költséggel jár, azt nevezhetjük a legrövidebb út algoritmusának.

Itt a „költség” az útvonal csomópontjainak számát vagy az egyes útvonalakon lévő költségek összegét jelenti. Egy útvonalnak egy vagy több éle lehet. A két csúcs közötti kapcsolatot élnek nevezzük. Különféle típusú legrövidebb útvonalú algoritmusok léteznek, például Dijkstra algoritmusa, Bellman-Ford algoritmus stb.

Itt a Dijkstra algoritmusáról beszélünk

Nézzük a következő súlyozott grafikont:

A „súlyozott” kifejezés a költségek egyik csomópontról a másikra való áthelyezését jelenti. Például az 1. csomópontról a 2. csomópontra lépve a költség vagy a súly 1.
Az 1-es csomópont és a 2-es csomópont közötti utat élnek nevezzük.
Az „iránytalan” azt jelenti, hogy áthelyezhet egy csomópontot a másikba, majd vissza az előző csomópontra. Tehát, ha megpróbáljuk megtalálni az összes útvonalat az 1-es csomóponttól a 7-es csomópontig, akkor ez lesz:

Útvonal vagy útvonal	Költség
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

Ebből a négy útvonalból láthatjuk, hogy az első út 7-be fog kerülni. Tehát költség szempontjából ez a legrövidebb út.

Hogyan működik Dijkstra algoritmusa

A Dijkstra algoritmus képes megtalálni a legrövidebb távolságot irányított és irányítatlan súlyozott gráfokban egyaránt. Ez az algoritmus mohó, mert mindig a legrövidebb vagy legközelebbi csomópontot választja az origóból. A „mohó” kifejezés azt jelenti, hogy az eredmények vagy eredmények halmaza közül az algoritmus a legjobbat választja ki közülük.

Itt igyekszünk megtalálni a legrövidebb utakat az összes többi útvonal közül. Tehát a Dijkstra algoritmusa megtalálja az összes legrövidebb utat egyetlen célcsomóponttól. Ennek eredményeként úgy viselkedik, mint a mohó algoritmus.

Az alábbi „példa” részben lépésről lépésre láthatja a megközelítést. A következőképpen működik:

Step 1) Inicializálja a kezdő csomópontot 0 költséggel, a csomópont többi részét pedig végtelen költséggel.
Step 2) Tartson fenn egy tömböt vagy listát a meglátogatott csomópontok nyomon követéséhez
Step 3) Frissítse a csomópont költségét a minimális költséggel. Megtehető az aktuális költség és az útköltség összehasonlításával. (A bemutató a példa részben látható)
Step 4) Folytassa a 3. lépést, amíg az összes csomópontot meg nem látogatja.

Mindezen lépések elvégzése után megtaláljuk azt az utat, amely minimális költséggel jár a forrástól a célig.

Különbség a Dijkstra és a BFS, DFS között

A fő különbség a Dijkstra és a BFS-DFS között az, hogy a Dijkstra a legrövidebb útkereső algoritmus, a BFS, DFS pedig az útkereső algoritmus. Általában a BFS és a DFS nem veszi figyelembe a költségeket az útvonal megtalálásakor. Tehát ezek az algoritmusok nem tudják garantálni a legrövidebb utat.

2D rács bemutató a BFS működéséről

Ez a demonstráció azt jelzi, hogy a BFS csak az utat találja meg. Azonban nem törődik az ösvény súlyával. BFS (Breadth-First Search) feltételezi, hogy az egyik csomópontból a másikba való utazás csak 1-be kerül.

De lássunk egy példagrafikont:

Itt talál egy utat a 2. szinten. A BFS a grafikonon szintrendben halad. Tehát így utazik:

Step 1) Kezdje az „1” csomóponttól, és keresse fel az összes szomszédos 2,3,4, XNUMX, XNUMX csomópontot

Step 2) Jelölje meg a 2,3,4., 1., XNUMX. csomópontot XNUMX. szintként, és keresse fel a szomszédos csomópontjaikat. Folytatja az összes szomszédos csomópont feltárását, amíg el nem éri a célcsomópontot.

Az elosztott fájlrendszer szempontjából az 1-től 7-ig terjedő útvonalat a következőképpen haladja meg:

1→2→3→7 (eredeti költség 10, DFS költség 3)
1→2→6→7 (eredeti költség 7, DFS költség 3)
1→3→7 (Eredeti költség 8, DFS költség 2)
1→4→5→7 (eredeti költség 13, DFS költség 3)

Amint látjuk, a DFS a mélység vagy az élek számával számítja ki az útköltséget.

A DFS a következőket teszi:

Az elosztott fájlrendszer megtalálja a forrástól (a kezdőcsúcstól) a célig vezető utat.
Nem tudja garantálni, hogy a forráscsomóponttól a célig felfedezett út a legrövidebb út-e vagy sem.

A Dijkstra algoritmus szempontjából azonban a költségük alapján választja ki az éleket. Mohó algoritmusként a legjobb vagy a minimális költségű utat választja ki.

Példa Dijkstra algoritmusára

A Dijkstra algoritmusa a költséget vagy a súlyt használja az útvonal teljes költségének kiszámításához.

A Dijkstra algoritmusának célja ennek a teljes költségnek vagy súlynak a minimalizálása. A fenti példában megtaláljuk a legjobb útvonalakat az 1. csomóponttól a 7. csomópontig, majd kiszámítjuk az összes költséget.

A Dijkstra algoritmusában súlyszámítással találja meg a legrövidebb utakat. Nem fog minden lehetséges utat megkeresni. Mutassuk meg Dijkstra algoritmusát egy példán keresztül. Például arra kérték, hogy keresse meg a legrövidebb utat az 1-es csomóponttól a 7-ig.

Ennek a folyamatnak a lépései az alábbiak:

Step 1) Inicializálja a kezdő csomópont költségét 0-ra.

A csomópont többi része, hozzárendelés „Inf”. Ez azt jelenti, hogy nincs út a kezdő csúcs (a forrás) és a csomópont között, vagy az útvonal még nincs meglátogatva.

Step 2) Amikor kiválasztja az 1. csomópontot, a rendszer látogatottként jelöli meg. Ezután frissítse az 1. csomópont összes szomszédos szomszédját. 2,3,4 az 1. csomópont szomszédos csomópontjai.

A költség frissítése során az alábbi eljárást kell követnünk:

A fenti képlet segítségével frissíthetjük az egyes csomópontok költségét. Például az 1. csomópontnál voltunk, és frissítenünk kellett a szomszédos 2,3,4, XNUMX, XNUMX csomópont költségeit.

A frissítés után a költség vagy a súly így fog kinézni:

3. lépés) A „2” csomóponthoz a szomszédok a 6 és a 3. A költséget „6”-ra frissítjük a végtelen (aktuális érték) összehasonlításával. A 2. csomópont költsége + az útvonal költsége 2-től 6-ig. Egyszerűen mondva, a „6” csomópont költsége 1+3 vagy 4 lesz.

A 3. csomópont a 2. csomópont szomszédja. Az előző lépésben azonban kiszámoltuk a költségét, ami 7 volt. Most, ha az útvonalunk 1-2-3, a 3. csomópont költsége 10 lesz. 1-2- 3 ára 10, míg 1-3 7.

4. lépés) A 3. csomóponthoz a szomszédos csomópont 7. Tehát a 7. csomópont aktuális értékét összehasonlítva az útköltséggel (7+1) vagy 8-mal, frissítjük a 7. csomópont költségét. Ez a 8.

Tehát találunk egy utat az 1-es csomóponttól a 7-es csomópontig, és ez 1→3→7. A költség 8.

5. lépés) A 4. csomóponthoz ennek megfelelően frissítjük a szomszédos csomópont költségét. Tehát az „5” csomópont frissített költsége 8 lesz. A 4,5 lépés után ez így fog kinézni:

Most az 1-3-7 útvonal ára 8 volt (korábban). A „7” csomópont nem lett meglátogatott, mert a „7” csomópontot a „6” csomópontból tudjuk elérni. Az „1-2-6” útvonal költsége 4 volt. Tehát az 1-2-6-7 útvonal költsége 7 lesz.

Mivel 7 < 8, ezért az „1” forráscsúcstól a „7” célcsúcsig a legrövidebb út 1-2-6-7 lesz, a költség pedig 7. Korábban 1-3-7 volt, és a költség 8 volt.

Tehát a végső grafikon így fog kinézni:

A fekete vonallal jelölt él a legrövidebb utunk 1-től 7-ig, és 7-be fog kerülni.

Pseudo Code Dijkstra algoritmusa

Íme a Dijkstra algoritmusának pszeudokódja

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++ Dijkstra algoritmusának megvalósítása

Dijkstra algoritmusának megvalósításához a C++, itt a kód:

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

output:

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 Dijkstra algoritmusának megvalósítása

Dijkstra algoritmusának megvalósításához a piton, itt a kód:

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)

output:

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

Láthatjuk, hogy az Algoritmus a forráscsomóponttól számított legrövidebb távolságot számítja ki.

Dijkstra algoritmus alkalmazása

A Dijkstra Algo számos felhasználási területtel rendelkezik. Ezek közül széles körben használják a hálózatépítés területén. Íme néhány a Dijkstra algoritmus valós használatából:

Dijkstra a Google térképen: Alapvetően ez az algoritmus a gerince a legrövidebb utak megtalálásának. Ahogy a fenti kódrészlet kimenetéből láthatjuk.

A Google nem az egyszerű Dijkstra algoritmust használja. Ehelyett egy módosított verziót használ. Amikor kiválaszt egy úti célt, több útvonalat is megjelenít a Google Térképen. Ezen elérési utak közül néhányat a rendszer a felhasználó számára rendez. Ezek a kiválasztott utak az „idő” alapján történtek. Tehát az „idő” a legrövidebb út szélső költsége.

Dijkstra az IP-útválasztásban: IP-útválasztás egy hálózati terminológia. Ez azt jelenti, hogy az Ön adatcsomagja hogyan kerül elküldésre a vevőnek különböző utakon. Ezek az útvonalak útválasztókat, szervereket stb. tartalmaznak. Az IP-útválasztásban különböző típusú protokollok léteznek.

Ezek a protokollok segítenek az útválasztónak megtalálni a legrövidebb útvonalat az adatok küldéséhez. Az egyik protokoll neve „OSPF (Open Shortest Path First)”. Az OSPF dijkstra algoritmust használ. A router vezet egy útvonaltáblázatot. Minden útválasztó megosztja a táblázatát a szomszédos útválasztókkal. A frissített táblázat kézhezvétele után újra ki kell számítaniuk az összes elérési utat. Ekkor az útválasztó a Dijkstra algoritmust használja.

Dijkstra algoritmusának korlátozása

A Dijkstra algoritmus nem tudja garantálni a legrövidebb utat a negatív élgráfban. A Dijkstra algoritmus a következő módszereket követi:

Az egyik legrövidebb út az egyik csomóponttól a másikig vezet.
A két csomópont közötti legrövidebb út kiválasztása után a rendszer nem számítja ki újra.

Itt figyeljen meg két negatív élű példát.

A bal oldali grafikonon három csúcs van. A Dijkstra a következőképpen fog futni a grafikonon:

Step 1) Az „1” kezdőcsúcs nullára lesz inicializálva. A többi csomópont végtelen lesz.

Step 2) Jelölje meg az „1” csomópontot látogatottként, és vegye fel a legrövidebb útvonalba.

Step 3) Az 1-es forráscsomópont távolsága a „2” és „3” csomópontoktól a végtelenbe van állítva, mivel a legrövidebb utat még ki kell számítani. Tehát minden olyan út, amely a végtelennél kevesebbe kerül, hozzáadódik a legrövidebb úthoz (mohó megközelítés).

Step 4) Az „1” forráscsúcs vagy a forráscsomópont távolságának frissítése „2”-re. A jelenlegi súly 5 (5

Step 5) Ha most megvizsgáljuk a legrövidebb távolságokat az „1” csomóponttól, azt találjuk, hogy az 5 az 1–> 2 él legrövidebb távolsága. Tehát a „2” csomópont látogatottként lesz megjelölve.

Hasonlóképpen, a „3” csomópont is látogatottként lesz megjelölve, mivel a legrövidebb távolság a 3.

Azonban, ha megfigyeljük, van egy 1-3-2 út, ami csak 2-be kerül. De a Dijkstra azt mutatja, hogy az „1” csomóponttól a „2” csomópontig a legrövidebb távolság 5. Tehát Dijkstra nem tudta kiszámítani a legrövidebbet távolságot helyesen. Ennek az az oka, hogy a Dijkstra egy mohó algoritmus. Tehát, ha egy csomópont látogatottnak van jelölve, a rendszer nem vizsgálja felül, bár lehet, hogy rövidebb elérési út áll rendelkezésre. Ez a probléma csak akkor fordul elő, ha az élek negatív költséggel vagy negatív súlyú élekkel rendelkeznek

A Dijkstra ebben a forgatókönyvben nem tudja kiszámítani a két csomópont közötti legrövidebb utat. Ennek eredményeképpen ennek az algoritmusnak vannak hátrányai. A negatív élprobléma megoldására egy másik „Bellman-Ford Algorithm” nevű algoritmust használnak. Ez az algoritmus negatív élekkel is működhet.

Dijkstra algoritmusának összetettsége

A fenti megvalósítás két „for” hurkot használt. Ezek a hurkok a csúcsok számára futnak. Tehát az idő bonyolultsága O(V²). Itt a „0” kifejezés olyan jelölést jelent, amely a Dijkstra algoritmusra vonatkozó feltételezést ad.

A grafikont a „Priority Queue” segítségével tárolhatjuk. A prioritási sor egy bináris kupac adatstruktúra. Hatékonyabb lesz, mint egy 2D mátrix. A minimális költséggel rendelkező él kiemelt prioritást élvez.

Akkor az idő bonyolultsága lesz O(E log(V)). Itt E az élek száma, V pedig a csúcsok száma.

A tér összetettsége az O(V²), mivel szomszédsági mátrixot használunk (2D tömb). A tér összetettsége optimalizálható szomszédsági lista vagy sor adatstruktúra segítségével.

Talán tetszene: