Dijkstra algoritm Python & C++ (Näide)

Mis on lühim tee või lühim vahemaa?

Tee lähtetipust sihttippu, mis maksab minimaalselt, on lühim tee või lühim vahemaa. Graafiteoorias on võimalik, et lähtest sihtkohta on mitu marsruuti. Nende marsruutide hulgast, kui leidub marsruut, mis maksab minimaalselt, nimetame seda lühimaks teeks.

Siin tähendab „maksumus” marsruudil olevate sõlmede arvu või iga serva kulude summat. Teel võib olla üks või mitu serva. Kahe tipu vahelist ühendust nimetatakse „servaks”. On olemas erinevat tüüpi lühima tee algoritme, näiteks Dijkstra algoritm ja Bellman-Fordi algoritm.

Siin arutame Dijkstra algoritmi. Vaatleme järgmist kaalutud graafikut:

Suunamata kaalutud graafik

• Mõiste „kaalutud” tähendab ühest sõlmest teise liikumise kulu. Näiteks sõlmest 1 sõlme 2 liikumisel on kulu ehk kaal 1.
• Tee sõlmede 1 ja 2 vahel nimetatakse servaks.
• „Suunamata” tähendab, et saate liikuda ühest sõlmest teise ja tagasi eelmisesse sõlme. Seega, kui proovime leida kõik marsruudid sõlmest 1 sõlme 7, on need järgmised:

Nende nelja marsruudi hulgast näeme, et esimene marsruut maksab 7. Seega on see maksumuse poolest lühim tee.

Lühim tee

Kuidas Dijkstra algoritm töötab

Dijkstra algoritm suudab leida lühima vahemaa nii suunatud kui ka suunamata kaalutud graafikutes. See algoritm on ahne, kuna see valib alati lühima või alguspunktist lähima sõlme. Mõiste „ahne” tähendab, et algoritm valib tulemuste hulgast parima.

Siin püüame leida lühimaid teid kõigi teiste marsruutide hulgast. Seega leiab Dijkstra algoritm kõik lühimad teed ühest lähtesõlmest. Selle tulemusena käitub see nagu ahne algoritm.

Allolevas näiteosas näete samm-sammult lähenemist. See toimib järgmiselt:

Step 1) Initsialiseeri algsõlm hinnaga 0 ja ülejäänud sõlmed hinnaga lõpmatuseni.
Step 2) Massiivi või loendi haldamine track külastatud sõlmedest.
Step 3) Uuenda sõlme maksumust minimaalse maksumusega. Seda saab teha, võrreldes praegust maksumust tee maksumusega (näidatud näiteosas).
Step 4) Jätka 3. sammuga, kuni kõik sõlmed on külastatud.

Pärast kõigi nende sammude sooritamist leiame tee, mis maksab allikast sihtkohta minimaalselt.

Erinevus Dijkstra ja BFS, DFS vahel

Peamine erinevus Dijkstra ja BFS-DFS vahel on see, et Dijkstra on lühima tee leidmise algoritm, samas kui BFS ja DFS on üldised tee leidmise algoritmid. Üldiselt ei arvesta BFS ja DFS tee leidmisel servakulu. Seega ei saa need algoritmid garanteerida lühimat teed.

BFS-i toimimise 2D-ruudustiku demonstratsioon

Algosketš, mis näitab BFS-i demonstratsiooni

See demonstratsioon näitab, et BFS leiab ainult tee. See aga ei hooli raja kaalust. BFS (Breadth-First Search) eeldab, et ühest sõlmest teise sõitmine maksab ainult 1.

Vaatame näidisgraafikut:

Siin leiab BFS tee 2. tasemelt. BFS läbib graafi taseme järjekorras. Seega liigub see nii:

Step 1) Alusta sõlmest "1" ja külasta kõiki külgnevaid sõlmi 2, 3, 4.

Step 2) Märgi sõlmed 2, 3 ja 4 1. taseme sõlmedeks ja külasta nende kõrvalasuvaid sõlmi. See jätkab kõigi külgnevate sõlmede uurimist, kuni jõuab sihtsõlmeni.

DFS-i osas läbib see tee vahemikus 1 kuni 7 järgmiselt:

• 1→2→3→7 (algne maksumus 10, DFS-i maksumus 3)
• 1→2→6→7 (algne maksumus 7, DFS-i maksumus 3)
• 1→3→7 (algne hind 8, DFS-i maksumus 2)
• 1→4→5→7 (algne maksumus 13, DFS-i maksumus 3)

Nagu näeme, arvutab DFS oma tee maksumuse servade arvuga. DFS teeb järgmist:

• DFS suudab leida tee allikast (algustipp) sihtkohta.
• See ei saa garanteerida, kas lähtesõlmest sihtkohta avastatud tee on lühim või mitte.

Dijkstra algoritmi kohaselt valib see servad aga nende maksumuse põhjal. Ahne algoritmina valib see minimaalse maksumusega teed.

Dijkstra algoritmi näide

Dijkstra algoritm kasutab tee kogumaksumuse arvutamiseks kulu või kaalu.

Dijkstra algoritmi eesmärk on minimeerida kogukulu või kaal. Ülaltoodud näites leiame parimad teed sõlmest 1 kuni sõlme 7, seejärel arvutame kõik kulud.

Dijkstra algoritm leiab lühimad teed kaalude arvutamise teel. See ei otsi kõiki võimalikke teid. Demonstreerime Dijkstra algoritmi näitega. Näiteks palutakse teil leida lühim tee sõlmest 1 sõlme 7.

Selle protsessi jaoks on toodud järgmised sammud:

Step 1) Initsialiseeri algse sõlme maksumuseks 0. Määra "Inf" ülejäänud sõlmedele. See tähendab, et allika ja sõlme vahel puudub tee või teed pole veel külastatud.

Step 2) Kui valite sõlme 1, märgitakse see külastatuks. Seejärel värskendage kõiki sõlme 1 külgnevaid naabreid. 2, 3 ja 4 on sõlme 1 naabersõlmed.

Kulude värskendamisel peame järgima allolevat protseduuri.

Saame iga sõlme maksumust uuendada ülaltoodud valemi abil. Näiteks olime sõlmes 1 ja pidime uuendama selle külgnevate sõlmede 2, 3 ja 4 maksumust. Pärast uuendamist näevad maksumused välja sellised:

Step 3) Sõlme „2“ naabrid on 6 ja 3. Uuendame maksumust „6“ juures, võrreldes lõpmatust (praegune väärtus) sõlme 2 maksumusega + tee maksumusega 2-st 6-ni. Lihtsamalt öeldes on sõlme „6“ maksumus 1 + 3 või 4.

Sõlm 3 on sõlme 2 naaber. Kuid me arvutasime selle maksumuse eelmises etapis, mis oli 7. Nüüd, kui meie tee on 1-2-3, on sõlm 3 maksumus 10. Tee 1-2- 3 maksab 10, samas kui 1 kuni 3 maksab 7.

Step 4) Sõlme 3 puhul on naabersõlm 7. Seega, võrreldes sõlme 7 praegust väärtust tee maksumusega (7+1) ehk 8, uuendame sõlme 7 maksumust. See on 8. Seega leiame tee sõlmest 1 sõlme 7 ja see on 1→3→7. Maksumus on 8.

Step 5) Sõlme 4 puhul uuendame vastavalt selle kõrvalasuva sõlme maksumust. Seega on sõlme „5” uuendatud maksumus 8. Pärast 4. ja 5. sammu näeb see välja selline:

Nüüd on tee 1-3-7 maksumus 8 (varem). Sõlme „7“ ei märgitud külastatuks, kuna me saame sõlme „7“ jõuda sõlmest „6“. Tee „1-2-6“ maksumus oli 4. Seega on tee 1-2-6-7 maksumus 7.

Kuna 7 < 8, on lühim tee lähtetipust „1“ sihttippu „7“ 1-2-6-7 ja maksumus on 7. Varem oli see 1-3-7 ja maksumus oli 8. Seega näeb lõplik graaf välja selline:

Musta joonega tähistatud serv on meie lühim tee 1-st 7-ni ja see maksab meile 7.

Pseudo Code Dijkstra algoritm

Siin on Dijkstra algoritmi pseudokood:

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 algoritmi rakendamine

Dijkstra algoritmi rakendamiseks kasutades C++, siin on kood:

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

Väljund:

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 algoritmi rakendamine

Dijkstra algoritmi rakendamiseks kasutades Python, siin on kood:

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)

Väljund:

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

Näeme, et algoritm arvutab lühima vahemaa lähtesõlmest.

Dijkstra algoritmi rakendamine

Dijkstra algoritmil on palju kasutusvõimalusi. Nende hulgas on see laialdaselt kasutusel võrgustamise valdkonnas. Siin on mõned Dijkstra algoritmi reaalsed kasutusviisid:

Dijkstra Google Kaardid: See algoritm on lühimate teede leidmise selgroog, nagu näeme ülaltoodud koodilõigu väljundist.

Google ei kasuta lihtsat Dijkstra algoritmi. Selle asemel kasutab see modifitseeritud versiooni. Sihtkoha valimisel kuvatakse teile mitu teed Google Kaardid. Nende teede hulgast on mõned kasutaja jaoks välja sorteeritud. Need teed valitakse aja põhjal. Seega on aeg lühima tee äärekulu.

Dijkstra IP-marsruutimises: IP-marsruutimine on võrguterminoloogia. See kirjeldab, kuidas teie andmepakett saadetakse vastuvõtjale erinevate teede kaudu. Need teed koosnevad ruuteritest, serveritest ja muudest seadmetest. IP-marsruutimises on erinevat tüüpi protokolle.

Need protokollid aitavad ruuteril leida lühimaid teid andmete saatmiseks. Üks protokolli nimetustest on „OSPF (Open Shortest Path First)”. OSPF kasutab Dijkstra algoritmi. Ruuter peab marsruutide tabelit. Iga ruuter jagab oma tabelit naaberruuteritega. Pärast uuendatud tabeli saamist peavad nad kõik teed uuesti arvutama. Sel ajal kasutab ruuter Dijkstra algoritmi.

Dijkstra algoritmi piirang

Dijkstra algoritm ei saa garanteerida lühimat teed negatiivsete servadega graafis. Dijkstra algoritm järgib järgmisi põhimõtteid:

• Ühest sõlmest teise viiakse üks lühim tee.
• Kui lühim tee kahe sõlme vahel on valitud, siis seda enam ei arvutata.

Siin on kaks negatiivsete servadega näidet.

Vasakpoolsel graafikul on kolm tippu. Dijkstra töötab graafikul järgmiselt:

Step 1) Algustipp “1” lähtestatakse nulliks. Teistel sõlmedel on lõpmatus.

Step 2) Märgi sõlm „1” külastatuks ja lisa see lühimasse teekonda.

Step 3) Allikasõlme 1 kaugus sõlmedest „2“ ja „3“ on seatud lõpmatuks, kuna lühimat teed pole veel arvutatud. Seega iga tee, mis maksab vähem kui lõpmatus, lisatakse lühimale teele (ahne lähenemine).

Step 4) Lähtetipu „1“ kauguse uuendamine punktile „2“. Praegune kaal on 5 (5 < lõpmatus). Samamoodi uuenda sõlme „1“ kaugus punktile „3“ kaaluga 3.

Step 5) Kui nüüd kontrollida lühimaid vahemaid sõlmest „1“, siis leiame, et serva 1→2 puhul on lühim vahemaa 5. Seega märgitakse sõlm „2“ külastatuks. Samamoodi märgitakse ka sõlm „3“ külastatuks, kuna lühim vahemaa on 3.

Kui aga vaatleme, siis on olemas tee 1-3-2, mis maksab ainult 2. Kuid Dijkstra näitab, et sõlmest "1" sõlme "2" on lühim vahemaa 5. Seega ei suutnud Dijkstra lühimat vahemaad õigesti arvutada. Põhjus on selles, et Dijkstra on ahne algoritm. Seega, kui sõlm on märgitud külastatuks, siis seda uuesti ei vaadata, kuigi võib olla saadaval lühem tee. See probleem ilmneb ainult siis, kui servadel on negatiivsed kulud või negatiivse kaaluga servad.

Dijkstra ei suuda selles stsenaariumis arvutada kahe sõlme vahelist lühimat teed. Seetõttu on sellel algoritmil mõned puudused. Selle negatiivse serva probleemi lahendamiseks kasutatakse teist algoritmi, mida nimetatakse Bellmani-Fordi algoritmiks. See algoritm saab töötada negatiivsete servadega.

Dijkstra algoritmi keerukus

Ülaltoodud teostus kasutas kahte for-silmust. Need tsüklid jooksevad tippude arvu jaoks. Niisiis, ajaline keerukus on O(V²)Siin on termin „O” tähistus, mis annab eelduse Dijkstra algoritmi jaoks.

Graafi saab salvestada "prioriteedijärjekorra" abil. Prioriteedijärjekord on binaarne kuhja andmestruktuur. See on efektiivsem kui 2D maatriks. Minimaalse hinnaga serval on kõrge prioriteet. Siis on ajaline keerukus O(E log V). Siin on E servade arv ja V on tippude arv.

Ruumi keerukus on O(V²), kuna me kasutame naabrusmaatriksit (2D massiiv). Ruumi keerukust saab optimeerida külgnemisloendi või järjekorra andmestruktuuri abil.

KKK