Dijsktra algoritm: C++, Python Koodinäide

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

Minimaalne tee lähtetipust sihtpunktini on lühim tee või lühim vahemaa. Graafikuteoorias on võimalik, et allikast sihtkohta on mitu marsruuti. Kui nende marsruutide vahel on marsruut, mis maksab minimaalselt, võime seda nimetada lühima tee algoritmiks.

Siin tähendab "kulu" marsruudi sõlmede arvu või iga tee kulude summeerimist. Teel võib olla üks või mitu serva. Ühendust kahe tipu vahel nimetatakse servaks. Lühima tee algoritme on erinevat tüüpi, näiteks Dijkstra algoritm, Bellman-Fordi algoritm jne.

Siin käsitleme Dijkstra algoritmi

Vaatame järgmist kaalutud graafikut:

• Mõiste "kaalutud" tähendab kulude teisaldamist ühest sõlmest teise. Näiteks liikudes sõlmest 1 sõlme 2, on maksumus või kaal 1.
• Teekonda sõlme 1 ja sõlme 2 vahel nimetatakse servaks.
• "Suunamatu" tähendab, et saate liigutada ühe sõlme teise ja tagasi eelmisele sõlmele. Niisiis, kui proovime leida kõik marsruudid sõlmest 1 kuni sõlme 7, siis on see:

Marsruut või tee	Maksma
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

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

Kuidas Dijkstra algoritm töötab

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

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

Allolevas jaotises „Näide” näete samm-sammult lähenemist. See toimib järgmiselt.

Step 1) Initsialiseerige lähtesõlm 0 kuluga ja ülejäänud sõlm kui Infinity Cost.
Step 2) Külastatud sõlmede jälgimiseks hoidke massiivi või loendit
Step 3) Värskendage sõlme maksumust minimaalse kuluga. Seda saab teha, võrreldes praegust maksumust tee maksumusega. (Esitlus on näidatud näidete jaotises)
Step 4) Jätkake sammu 3, kuni kogu sõlm 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 seisneb selles, et Dijkstra on lühim teeotsingu algoritm ja BFS, DFS on rajaotsingu algoritm. Üldjuhul ei arvesta BFS ja DFS tee leidmisel kuludega. Seega ei saa need algoritmid tagada lühimat teed.

2D-ruudustiku demonstratsioon BFS-i toimimise kohta

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.

Kuid vaatame näidet graafikust:

Siin leiab ta tee 2. tasemel. BFS läbib graafiku taseme järjekorras. Niisiis, see reisib nii:

Step 1) Alustage sõlmest "1" ja külastage kõiki külgnevaid sõlmi 2,3,4, XNUMX, XNUMX

Step 2) Märkige sõlm 2,3,4, 1, XNUMX tasemel XNUMX ja külastage nende külgnevaid sõlmi. See jätkab kõigi külgnevate sõlmede uurimist, kuni jõuab sihtkoha sõlme.

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 sügavuse või servade arvu järgi.

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 osas valib see aga servad nende maksumuse alusel. Ahne algoritmina valib see parima või minimaalse kuluga tee.

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 algoritmis leiab see kaalude arvutamise teel lühimad teed. See ei otsi kõiki võimalikke teid. Demonstreerime näitega Dijkstra algoritmi. Näiteks on teil palutud leida lühim tee sõlmest 1 kuni 7.

Selle protsessi jaoks on toodud järgmised sammud:

Step 1) Lähtestage lähtesõlme maksumus 0-ks.

Ülejäänud sõlm, määrake "Inf". See tähendab, et algustipu (allika) ja sõlme vahel pole teed 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 naabernaabreid. 2,3,4 on sõlme 1 naabersõlmed.

Kulude värskendamisel peame järgima allolevat protseduuri.

Saame ülaltoodud valemi abil värskendada iga sõlme maksumust. Näiteks olime sõlmes 1 ja meil oli vaja värskendada selle külgneva sõlme 2,3,4 maksumust.

Pärast värskendamist näeb maksumus või kaal välja järgmine:

Samm 3) Sõlme "2" jaoks naabrid on 6 ja 3. Värskendame maksumust väärtusele 6, võrreldes lõpmatust (praegune väärtus). Sõlme 2 hind + tee maksumus 2 kuni 6. Lihtsalt ö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.

4. samm) 3. sõlme jaoks naabersõlm on 7. Seega, võrreldes sõlme 7 hetkeväärtust teemaksumusega (7+1) või 8, uuendame sõlme 7 maksumust. See on 8.

Niisiis, leiame tee sõlmest 1 sõlme 7 ja see on 1 → 3 → 7. Maksumus on 8.

5. samm) 4. sõlme jaoks värskendame selle külgneva sõlme maksumust vastavalt. Seega on sõlme 5 värskendatud maksumuseks 8. Pärast sammu 4,5 näeb see välja järgmine:

Nüüd on tee 1-3-7 hind 8 (varem). Sõlme “7” ei märgitud külastatuks, sest sõlmest “7” jõuame sõlme “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” sihttipuni 7-1-2-6 ja maksumus on 7. Varem oli see 7-1-3 ja maksumus oli 7.

Niisiis, lõplik graafik näeb välja selline:

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

Pseudokood Dijkstra algoritm

Siin on Dijkstra algoritmi pseudokood

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

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 püüton, 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] & 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)

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 kauguse lähtesõlmest.

Dijkstra algoritmi rakendamine

Dijkstra Algol on palju kasutusvõimalusi. Nende hulgas kasutatakse seda laialdaselt võrkude loomisel. Siin on mõned Dijkstra algoritmi tegelikud kasutusviisid:

Dijkstra Google'i kaardil: Põhimõtteliselt on see algoritm lühimate teede leidmise selgroog. Nagu näeme ülaltoodud koodilõigu väljundist.

Google ei kasuta lihtsat Dijkstra algoritmi. Selle asemel kasutab see muudetud versiooni. Kui valite sihtkoha, kuvab see teile Google'i kaardil mitut teed. Nende teede hulgast on mõned teed kasutaja jaoks välja sorteeritud. Need valitud teed põhinevad "ajal". Seega on "aeg" lühima tee äärekulu.

Dijkstra IP-marsruutimisel: IP-marsruutimine on võrgustikutöö terminoloogia. See tähendab, kuidas teie andmepakett saadetakse vastuvõtjale erinevaid teid pidi. Need teed koosnevad ruuteritest, serveritest jne. IP-marsruutimisel on erinevat tüüpi protokolle.

Need protokollid aitavad ruuteril leida lühimad teed andmete saatmiseks. Üks protokollinimedest on "OSPF (Ava lühim tee kõigepealt)". OSPF kasutab dijkstra algoritmi. Ruuter haldab marsruutide tabelit. Iga ruuter jagab oma tabelit naabrite ruuteritega. Pärast värskendatud 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 negatiivse serva graafikus. Dijkstra algoritm järgib järgmisi metoodikaid:

• Ü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 seal 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ärkige sõlm "1" külastatuks ja lisage see lühimasse teekonda.

Step 3) Lähtesõlme 1 kaugus sõlmedest 2 ja 3 on seatud lõpmatuseni, kuna lühim tee on veel arvutamata. Niisiis, iga tee, mis maksab vähem kui lõpmatus, lisatakse lühimale teele (ahne lähenemine).

Step 4) Vahemaa värskendamine lähtetipust või lähtesõlmest “1” väärtuseks “2”. Praegune kaal on 5 (5

Step 5) Nüüd, kui kontrollime lühimaid kaugusi sõlmest “1”, leiame, et 5 on serva 1–> 2 lühim vahemaa. Seega märgitakse sõlm “2” külastatuks.

Samamoodi märgitakse külastatuks ka sõlm “3”, kuna lühim vahemaa on 3.

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

Dijkstra ei suuda selle stsenaariumi korral arvutada lühimat teed kahe sõlme vahel. Sellest tulenevalt on sellel algoritmil mõned puudused. Selle negatiivse serva probleemi lahendamiseks kasutatakse teist algoritmi nimega “Bellman-Ford Algorithm”. See algoritm võib 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 tähendab termin "0" tähistust, mis annab eelduse Dijkstra algoritmi jaoks.

Graafiku saame salvestada "Priority Queue" abil. Prioriteetne järjekord on binaarne hunniku andmestruktuur. See on tõhusam kui 2D-maatriks. Minimaalsete kuludega 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.