Dijkstra algoritmusa Python & C++ (Példa)

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

A forráscsúcstól a célcsúcsig vezető, minimális költséggel járó út a legrövidebb út vagy legrövidebb távolság. A gráfelméletben lehetséges, hogy egy forráscsúcstól a célig több útvonal is legyen. Ezen útvonalak közül, ha van egy, amelyik minimális költséggel jár, azt a legrövidebb útnak nevezzük.

Itt a „költség” az útvonalban lévő csomópontok számát vagy az egyes élek költségeinek összegét jelenti. Egy útvonalnak lehet egy vagy több éle. Két csúcs közötti kapcsolatot „élnek” nevezzük. Különböző típusú legrövidebb út algoritmusok léteznek, például a Dijkstra algoritmus és a Bellman-Ford algoritmus.

Itt a Dijkstra algoritmust tárgyaljuk. Nézzük meg a következő súlyozott gráfot:

Irányítatlan súlyozott grafikon

• A „súlyozott” kifejezés az egyik csomópontról a másikra való áthelyezés költségét jelenti. Például az 1-es csomópontról a 2-es csomópontra való áthelyezés esetén a költség vagy súly 1.
• Az 1-es és 2-es csomópont közötti utat élnek nevezzük.
• Az „irányítatlan” azt jelenti, hogy az egyik csomópontról a másikra, majd vissza az előző csomópontra lehet lépni. Tehát, ha megpróbáljuk megtalálni az összes útvonalat az 1-es csomóponttól a 7-es csomópontig, akkor azok a következők lesznek:

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

A legrövidebb út

Hogyan működik Dijkstra algoritmusa

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

Itt a legrövidebb útvonalakat próbáljuk megtalálni az összes többi útvonal közül. Tehát a Dijkstra algoritmus egyetlen forráscsomópontból kiindulva megkeresi az összes legrövidebb utat. Ennek eredményeként úgy viselkedik, mint egy mohó algoritmus.

Az alábbi „példa” részben lépésről lépésre bemutatjuk a módszert. A következőképpen működik:

Step 1) Inicializáld a kezdő csomópontot 0 költséggel, a többi csomópontot pedig végtelen költséggel.
Step 2) Tömb vagy lista karbantartása traca meglátogatott csomópontok k.
Step 3) Frissítse a csomópont költségét a minimális költséggel. Ez úgy tehető meg, hogy összehasonlítja az aktuális költséget az útvonal költségével (lásd a példa részben).
Step 4) Folytassa a 3. lépést, amíg az összes csomópontot meg nem látogatta.

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 Dijkstra és a BFS-DFS közötti fő különbség az, hogy a Dijkstra egy legrövidebb útkereső algoritmus, míg a BFS és a DFS általános útkereső algoritmusok. Általános esetekben a BFS és a DFS nem veszi figyelembe az élköltséget az út keresésekor. Tehát ezek az algoritmusok nem garantálják a legrövidebb utat.

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

Algosketch, BFS bemutatót mutat

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.

Nézzünk egy példa grafikont:

Itt a BFS egy 2. szintű utat talál. A BFS szint sorrendben halad be a gráfot. Tehát így halad:

Step 1) Kezdje az „1” csomóponttal, és látogassa meg az összes szomszédos 2, 3, 4 csomópontot.

Step 2) Jelöld meg a 2., 3., 4. csomópontokat 1. szintűként, és látogassd meg a szomszédos csomópontjaikat. Továbbra is felderíti az összes szomszédos csomópontot, 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 az élek számával számítja ki az útköltségét. 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 értelmében azonban az éleket a költségük alapján választja ki. Mohó algoritmusként a minimális költségű útvonalakat 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 súlyok kiszámításával találja meg a legrövidebb utakat. Nem fog minden lehetséges utat megkeresni. Nézzük meg a Dijkstra algoritmust egy példával. Például arra kértek, hogy találd meg a legrövidebb utat az 1-es és 7-es csomópont között.

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

Step 1) Inicializálja a kezdő csomópont költségét 0-ra. Rendeljen hozzá „Inf” a többi csomóponthoz. Ez azt jelenti, hogy nincs útvonal a forrás és a csomópont között, vagy az útvonalat még nem látogatták meg.

Step 2) Amikor kiválasztod az 1-es csomópontot, az meglátogatottként lesz megjelölve. Ezután frissítsd az 1-es csomópont összes szomszédját. A 2, 3 és 4 az 1-es 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éplettel frissíthetjük az egyes csomópontok költségét. Például az 1-es csomópontnál voltunk, és frissítenünk kellett a szomszédos 2-es, 3-as és 4-es csomópontok költségét. A frissítés után a költségek így fognak kinézni:

Step 3) A „2” csomópont szomszédai a 6 és a 3. A „6”-os költséget úgy frissítjük, hogy a végtelent (jelenlegi érték) összehasonlítjuk a 2. csomópont költségével + a 2-től 6-ig tartó út költségével. Egyszerűen fogalmazva, 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.

Step 4) A 3-as csomópont esetében a szomszédos csomópont a 7. Tehát, ha összehasonlítjuk a 7-es csomópont aktuális értékét az útvonal költségével (7+1), azaz 8-cal, frissítjük a 7-es csomópont költségét. Ez 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.

Step 5) A 4-es csomópont esetében 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. és 5. lépés után így fog kinézni:

Most az 1-3-7 útvonal költsége 8 (korábban). A „7” csomópontot nem jelöltük látogatottként, mert a „7” csomópontot a „6” csomópontból is elérhetjük. 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, a legrövidebb út az „1” forráscsúcstól a „7” célcsúcsig 1-2-6-7 lesz, a költség pedig 7. Korábban 1-3-7 volt, a költség pedig 8. Tehát a végső gráf í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.

Pszeudo Code Dijkstra algoritmusa

Itt van a Dijkstra-algoritmus pszeudokódja:

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++ 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] && 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);
}

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

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 kiszámítja a forráscsomóponttól való legrövidebb távolságot.

Dijkstra algoritmus alkalmazása

A Dijkstra algoritmus számos felhasználási területen alkalmazható. Ezek közül széles körben alkalmazzák a hálózatépítés területén. Íme néhány valós felhasználási példa a Dijkstra algoritmusra:

Dijkstra Google Térképek: Ez az algoritmus a legrövidebb utak megtalálásának gerincét alkotja, amint azt a fenti kódrészlet kimenetéből is láthatjuk.

Google nem az egyszerű Dijkstra algoritmust használja. Ehelyett egy módosított verziót használ. Amikor kiválaszt egy célállomást, több útvonalat is megjelenít Google Térképek. Ezen útvonalak közül néhányat a felhasználó számára rendeztek. Ezeket az útvonalakat az „idő” alapján választják ki. Tehát az „idő” a legrövidebb útvonal élköltsége.

Dijkstra az IP-útválasztásban: IP-útválasztás egy hálózati terminológia. Leírja, hogyan jut el az adatcsomag a címzetthez különböző útvonalakon keresztül. Ezek az útvonalak útválasztókból, szerverekből és egyéb berendezésekből állnak. Az IP-útválasztás során különböző típusú protokollok léteznek.

Ezek a protokollok segítenek az útválasztónak megtalálni a legrövidebb útvonalakat az adatok küldéséhez. Az egyik protokoll neve „OSPF (Előbb a legrövidebb útvonal megnyitása)”. Az OSPF Dijkstra algoritmust használ. Az útválasztó egy útvonaltáblázatot tart fenn. Minden útválasztó megosztja a táblázatát a szomszédos útválasztókkal. A frissített táblázat fogadása után újra ki kell számítaniuk az összes útvonalat. Ekkor az útválasztó Dijkstra algoritmust használ.

Dijkstra algoritmusának korlátozása

Dijkstra algoritmusa nem garantálja a legrövidebb utat egy negatív élű gráfban. Dijkstra algoritmusa a következő elveket 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 gráfon:

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

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

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

Step 4) Frissíti az „1” forráscsúcstól való távolságot „2”-re. Az aktuális súly 5 lesz (5 < végtelen). Hasonlóképpen frissítse az „1” csomóponttól „3”-ra való távolságot 3-as súllyal.

Step 5) Ha most megnézzük az „1” csomóponttól mért legrövidebb távolságokat, azt találjuk, hogy az 1→2 élhez tartozó legrövidebb távolság 5. Tehát a „2” csomópontot látogatottként jelöljük meg. Hasonlóképpen, a „3” csomópontot is látogatottként jelöljük meg, mivel a legrövidebb távolság 3.

Azonban, ha megfigyeljük, létezik egy 1-3-2 útvonal, amely csak 2-be kerül. Dijkstra azonban megmutatja, hogy az „1” csomóponttól a „2” csomópontig a legrövidebb távolság 5. Tehát Dijkstra nem tudta helyesen kiszámítani a legrövidebb távolságot. Ennek az az oka, hogy a Dijkstra egy mohó algoritmus. Tehát, ha egy csomópontot meglátogatottként jelölnek meg, akkor azt nem vizsgálják újra, bár lehet, hogy létezik egy rövidebb elérhető útvonal. Ez a probléma csak akkor jelentkezik, ha az élek negatív költségűek vagy negatív súlyúak.

Dijkstra ebben a forgatókönyvben nem tudja kiszámítani a legrövidebb utat két csomópont között. Ennek eredményeként ennek az algoritmusnak vannak hátrányai. A negatív élprobléma megoldására egy másik algoritmust, az úgynevezett „Bellman-Ford algoritmust” használják. Ez az algoritmus negatív élekkel is képes dolgozni.

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 az „O” kifejezés egy jelölés, amely a Dijkstra-algoritmushoz ad feltevést.

A gráfot egy „prioritási sor” segítségével tárolhatjuk. A prioritási sor egy bináris halom adatstruktúra. Hatékonyabb lesz, mint egy 2D mátrix. A minimális költségű él magas prioritású lesz. Ekkor az időbonyolultság a következő 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.

GYIK