Dijsktran algoritmi: C++, Python Koodiesimerkki

Mikä on lyhin polku tai lyhin etäisyys?

Vähimmäishintainen polku lähdepisteestä kohdepisteeseen on lyhin polku tai lyhin etäisyys. Graafiteoriassa on mahdollista, että lähteestä määränpäähän on useita reittejä. Jos näiden reittien välillä on reitti, joka maksaa vähimmäissumman, voimme kutsua sitä lyhimmän polun algoritmiksi.

Tässä "kustannus" tarkoittaa solmujen määrää reitillä tai kunkin polun kustannusten summaa. Polulla voi olla yksi tai useampi reuna. Kahden kärjen välistä yhteyttä kutsutaan "reunaksi". On olemassa erilaisia lyhimmän polun algoritmeja, kuten Dijkstran algoritmi, Bellman-Ford-algoritmi jne.

Täällä keskustelemme Dijkstran algoritmista

Katsotaanpa seuraavaa painotettua kuvaajaa:

Termi "painotettu" tarkoittaa kustannusten siirtämistä solmusta toiseen. Esimerkiksi siirryttäessä solmusta 1 solmuun 2, hinta tai paino on 1.
Polkua solmun 1 ja solmun 2 välillä kutsutaan reunaksi.
"Ohjaamaton" tarkoittaa, että voit siirtää solmun toiseen ja takaisin edelliseen solmuun. Joten jos yritämme löytää kaikki reitit solmusta 1 solmuun 7, se on:

Reitti tai polku	Hinta
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

Näistä neljästä reitistä voimme nähdä, että ensimmäinen reitti maksaa meille 7. Joten se on kustannusten suhteen lyhin reitti.

Kuinka Dijkstran algoritmi toimii

Dijkstra-algoritmi voi löytää lyhimmän etäisyyden sekä suunnatuissa että suuntaamattomissa painotetuissa kaavioissa. Tämä algoritmi on ahne, koska se valitsee aina lyhimmän tai lähimmän solmun origosta. Termi "ahne" tarkoittaa, että algoritmi valitsee niistä parhaan.

Täällä yritämme löytää lyhimmät polut kaikkien muiden reittien joukosta. Joten Dijkstran algoritmi löytää kaikki lyhyimmät reitit yhdestä kohdesolmusta. Tämän seurauksena se käyttäytyy kuin a ahne algoritmi.

Alla olevassa "esimerkki"-osiossa näet vaiheittaisen lähestymistavan. Se toimii seuraavasti:

Vaihe 1) Alusta aloitussolmu kustannuksilla 0 ja loput solmusta Infinity Costiksi.
Vaihe 2) Ylläpidä taulukkoa tai luetteloa seurataksesi vierailtuja solmuja
Vaihe 3) Päivitä solmun hinta minimikustannuksilla. Se voidaan tehdä vertaamalla nykyistä kustannuksia polun kustannuksiin. (Esittely näkyy esimerkkiosiossa)
Vaihe 4) Jatka vaihetta 3, kunnes kaikki solmu on käyty.

Kun kaikki nämä vaiheet on suoritettu, löydämme polun, joka maksaa vähintään lähteestä määränpäähän.

Ero Dijkstran ja BFS:n välillä, DFS

Suurin ero Dijkstran ja BFS-DFS:n välillä on, että Dijkstra on lyhin polunetsintäalgoritmi ja BFS, DFS on polunetsintäalgoritmi. Yleensä BFS ja DFS eivät ota huomioon kustannuksia polkua etsiessään. Joten nämä algoritmit eivät voi taata lyhintä polkua.

2D-ruudukkoesitys BFS:n toiminnasta

2D-ruudukon esittely — Algosketch, näyttää BFS-esittelyn

Tämä esittely osoittaa, että BFS löytää vain polun. Se ei kuitenkaan välitä polun painosta. BFS (Leveys - ensimmäinen haku) olettaa, että matka solmusta toiseen maksaa vain 1.

Mutta katsotaanpa esimerkkikaaviota:

Tässä se löytää polun tasolla 2. BFS kulkee Graphin läpi tasojärjestyksessä. Eli se kulkee näin:

Vaihe 1) Aloita solmusta “1” ja käy kaikissa vierekkäisissä solmuissa 2,3,4

Vaihe 2) Merkitse solmu 2,3,4 tasoksi 1 ja vieraile niiden vierekkäisissä solmuissa. Se jatkaa kaikkien vierekkäisten solmujen tutkimista, kunnes se saavuttaa kohdesolmun.

DFS:n suhteen se kulkee polun 1:stä 7:ään seuraavasti:

1→2→3→7 (alkuperäinen hinta 10, DFS hinta 3)
1→2→6→7 (alkuperäinen hinta 7, DFS hinta 3)
1→3→7 (alkuperäinen hinta 8, DFS-hinta 2)
1→4→5→7 (alkuperäinen hinta 13, DFS hinta 3)

Kuten näemme, DFS laskee polkukustannukset syvyyden tai reunojen lukumäärän perusteella.

DFS tekee seuraavaa:

DFS voi löytää polun lähteestä (alkupisteestä) määränpäähän.
Se ei voi taata, onko lähdesolmusta määränpäähän löydetty polku lyhin vai ei.

Dijkstra-algoritmin kannalta se kuitenkin valitsee reunat niiden kustannusten perusteella. Ahneena algoritmina se valitsee parhaan tai pienimmän kustannuspolun.

Esimerkki Dijkstran algoritmista

Dijkstran algoritmi käyttää kustannuksia tai painoa polun kokonaiskustannusten laskemiseen.

Dijkstran algoritmin tavoitteena on minimoida tämä kokonaiskustannus tai paino. Yllä esitetystä esimerkistä löydämme parhaat reitit solmusta 1 solmuun 7 ja laskemme sitten kaikki kustannukset.

Dijkstran algoritmissa se löytää lyhyimmät polut laskemalla painoja. Se ei etsi kaikkia mahdollisia polkuja. Esitetään Dijkstran algoritmi esimerkillä. Sinua on esimerkiksi pyydetty etsimään lyhin polku solmusta 1:een 7.

Tämän prosessin vaiheet on annettu alla:

Vaihe 1) Alusta aloitussolmun hinnaksi 0.

Loput solmusta, määritä "Inf". Se tarkoittaa, että aloituspisteen (lähde) ja solmun välillä ei ole polkua tai polulla ei ole vielä käyty.

Vaihe 2) Kun valitset solmun 1, se merkitään käydyksi. Päivitä sitten kaikki solmun 1 viereiset naapurit. 2,3,4 ovat solmun 1 naapurisolmut.

Kun päivitämme kustannuksia, meidän on noudatettava alla olevaa menettelyä:

Voimme päivittää kunkin solmun kustannukset yllä olevan kaavan avulla. Olimme esimerkiksi solmussa 1, ja meidän piti päivittää sen viereisen solmun 2,3,4 kustannukset.

Päivityksen jälkeen hinta tai paino näyttää tältä:

Vaihe 3) Solmulle "2", naapurit ovat 6 ja 3. Päivitämme hintaa arvoon "6" vertaamalla ääretöntä (nykyinen arvo). Solmun 2 hinta + polun hinta 2-6. Yksinkertaisesti sanottuna solmun "6" hinta on 1+3 tai 4.

Solmu 3 on solmun 2 naapuri. Laskimme kuitenkin sen kustannukset edellisessä vaiheessa, joka oli 7. Jos polkumme on nyt 1-2-3, solmun 3 hinta on 10. Polku 1-2- 3 maksaa 10, kun taas 1-3 maksaa 7.

Vaihe 4) Solmulle 3, naapurisolmu on 7. Joten vertaamalla solmun 7 nykyistä arvoa polun kustannuksiin (7+1) tai 8, päivitämme solmun 7 hintaa. Eli 8.

Joten löydämme polun solmusta 1 solmuun 7, ja se on 1 → 3 → 7. Hinta on 8.

Vaihe 5) Solmulle 4, päivitämme sen viereisen solmun kustannukset vastaavasti. Joten solmun "5" päivitetty hinta on 8. Vaiheen 4,5 jälkeen se näyttää tältä:

Nyt polun 1-3-7 hinta on 8 (aiemmin). Solmua "7" ei merkitty vierailluksi, koska voimme saavuttaa solmun "7" solmusta "6". Polun 1-2-6 hinta oli 4. Joten polun 1-2-6-7 hinta on 7.

Koska 7 < 8, siksi lyhin polku lähdepisteestä "1" kohdepisteeseen "7" on 1-2-6-7 ja hinta on 7. Aikaisemmin se oli 1-3-7 ja hinta oli 8.

Joten lopullinen kaavio näyttää tältä:

Mustalla viivalla merkitty reuna on lyhin polkumme 1 - 7, ja se maksaa meille 7.

Pseudo Code Dijkstran algoritmi

Tässä on pseudokoodi Dijkstran algoritmille

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++ Dijkstran algoritmin toteutus

Toteuttaa Dijkstran algoritmi käyttämällä C++, tässä on koodi:

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

lähtö:

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 Dijkstran algoritmin toteutus

Toteuttaa Dijkstran algoritmi käyttämällä pytonkäärme, tässä on koodi:

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)

lähtö:

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äemme, että algoritmi laskee lyhimmän etäisyyden lähdesolmusta.

Dijkstra-algoritmin soveltaminen

Dijkstra Algolla on suuri joukko käyttötarkoituksia. Niistä sitä käytetään laajalti verkottumisen alalla. Tässä on joitain Dijkstran algoritmin käyttötapoja tosielämässä:

Dijkstra Google-kartalla: Periaatteessa tämä algoritmi on selkäranka lyhimpien polkujen löytämiseen. Kuten voimme nähdä yllä olevasta koodinpätkän lähdöstä.

Google ei käytä yksinkertaista Dijkstra-algoritmia. Sen sijaan se käyttää muokattua versiota. Kun valitset määränpään, se näyttää sinulle useita polkuja Google-kartassa. Näistä poluista jotkut polut on lajiteltu käyttäjälle. Nämä valitut polut perustuvat "aikaan". Joten "aika" on lyhimmän polun reunakustannus.

Dijkstra IP-reitityksessä: IP-reititys on verkostoitumisterminologia. Se tarkoittaa, kuinka datapakettisi lähetetään vastaanottajalle eri polkuja pitkin. Nämä polut koostuvat reitittimistä, palvelimista jne. IP-reitityksessä on erilaisia protokollia.

Nämä protokollat auttavat reititintä löytämään lyhyimmat reitit tietojen lähettämiseen. Yksi protokollan nimistä on "OSPF (Open Shortest Path First)". OSPF käyttää dijkstra-algoritmia. Reititin ylläpitää reittitaulukkoa. Jokainen reititin jakaa taulukkonsa naapurireitittimien kanssa. Päivitetyn taulukon saatuaan heidän on laskettava kaikki polut uudelleen. Tuolloin reititin käyttää Dijkstra-algoritmia.

Dijkstran algoritmin rajoitus

Dijkstra-algoritmi ei voi taata lyhintä polkua negatiivisessa reunakaaviossa. Dijkstra-algoritmi noudattaa näitä menetelmiä:

Yksi lyhin polku viedään solmusta toiseen.
Kun lyhin polku kahden solmun välillä on valittu, sitä ei lasketa uudelleen.

Huomaa tässä kaksi esimerkkiä negatiivisilla reunoilla.

Vasemmassa kaaviossa kärkeä on kolme. Dijkstra toimii Graphissa seuraavasti:

Vaihe 1) Aloituspiste "1" alustetaan nollaan. Muilla solmuilla on ääretön.

Vaihe 2) Merkitse solmu "1" käydyksi ja sisällytä se lyhimpään polkuun.

Vaihe 3) Lähdesolmun 1 etäisyys solmuihin "2" ja "3" on asetettu äärettömyyteen, koska lyhin polku on vielä laskematta. Joten mikä tahansa polku, joka maksaa vähemmän kuin ääretön, lisätään lyhimpään polkuun (ahne lähestymistapa).

Vaihe 4) Päivitetään etäisyys lähdepisteestä tai lähdesolmusta "1" arvoon "2". Nykyinen paino on 5 (5

Vaihe 5) Jos nyt tarkistamme lyhyimmät etäisyydet solmusta "1", huomaamme, että 5 on reunan 1–> 2 lyhin etäisyys. Eli solmu 2 merkitään vierailluksi.

Samoin solmu "3" merkitään myös vierailluksi, koska lyhin etäisyys on 3.

Kuitenkin, jos havaitsemme, on olemassa polku 1-3-2, joka maksaa vain 2. Mutta Dijkstra osoittaa, että solmusta "1" solmuun "2" lyhin etäisyys on 5. Joten Dijkstra ei onnistunut laskemaan lyhimmän etäisyys oikein. Syy siihen on se, että Dijkstra on ahne algoritmi. Joten kun solmu on merkitty vierailluksi, sitä ei harkita uudelleen, vaikka käytettävissä voi olla lyhyempi polku. Tämä ongelma ilmenee vain, kun reunoilla on negatiiviset kustannukset tai negatiiviset painoreunat

Dijkstra ei pysty laskemaan lyhintä polkua kahden solmun välillä tässä skenaariossa. Tämän seurauksena tällä algoritmilla on joitain haittoja. Tämän negatiivisen reunaongelman ratkaisemiseksi käytetään toista algoritmia nimeltä "Bellman-Ford Algorithm". Tämä algoritmi voi toimia negatiivisten reunojen kanssa.

Dijkstran algoritmin monimutkaisuus

Yllä oleva toteutus käytti kahta "for"-silmukkaa. Nämä silmukat kulkevat pisteiden lukumäärällä. Aika monimutkaisuus on siis O(V²). Tässä termi "0" tarkoittaa merkintää, joka antaa oletuksen Dijkstra-algoritmista.

Voimme tallentaa kaavion "Priority Queue" -jonon avulla. Prioriteettijono on binäärikekotietorakenne. Se on tehokkaampi kuin 2D-matriisi. Reunalla, jonka kustannukset ovat mahdollisimman pienet, on korkea prioriteetti.

Silloin on aika monimutkaisuus O (E log (V)). Tässä E on reunojen lukumäärä ja V on kärkien lukumäärä.

Tilan monimutkaisuus on O(V²), koska käytämme vierekkäisyysmatriisia (2D-taulukko). Tilan monimutkaisuus voidaan optimoida vierekkäisyysluettelon tai jonotietorakenteen avulla.