Dijkstras algoritme i Python & C++ (Eksempel)

Hva er den korteste veien eller korteste avstanden?

En rute fra kildepunkten til destinasjonspunkten som koster et minimum er den korteste ruten eller korteste avstanden. I grafteori er det mulig å ha flere ruter fra en kilde til en destinasjon. Blant disse rutene, hvis det er en rute som koster et minimumsbeløp, kaller vi den den korteste ruten.

Her betyr «kostnad» antall noder i ruten eller summen av kostnader på hver kant. En bane kan ha én eller flere kanter. Forbindelsen mellom to hjørner kalles en «kant». Det finnes ulike typer korteste-bane-algoritmer, som Dijkstras algoritme og Bellman-Ford-algoritmen.

Her diskuterer vi Dijkstras algoritme. La oss se på følgende vektede graf:

En urettet-vektet graf

• Begrepet «vektet» betyr kostnaden ved å flytte fra én node til en annen. For eksempel, hvis man flytter fra node 1 til node 2, er kostnaden eller vekten 1.
• Banen mellom node 1 og node 2 kalles kanten.
• «Urettet» betyr at du kan bevege deg fra én node til en annen og tilbake til den forrige noden. Så hvis vi prøver å finne alle rutene fra node 1 til node 7, vil de være:

Blant disse fire rutene kan vi se at den første ruten koster 7. Så det er den korteste veien når det gjelder kostnader.

Korteste vei

Hvordan Dijkstras algoritme fungerer

Dijkstras algoritme kan finne den korteste avstanden i både rettede og ikke-rettede vektede grafer. Denne algoritmen er grådig fordi den alltid velger den korteste eller nærmeste noden fra origo. Begrepet «grådig» betyr at blant et sett med utfall eller resultater vil algoritmen velge det beste av dem.

Her prøver vi å finne de korteste stiene blant alle andre ruter. Dijkstras algoritme finner derfor alle de korteste stiene fra en enkelt kildenode. Som et resultat oppfører den seg som en grådig algoritme.

I «eksempel»-delen nedenfor ser du den trinnvise fremgangsmåten. Den fungerer slik:

Trinn 1) Initialiser startnoden med kostnad 0 og resten av nodene med uendelig kostnad.
Trinn 2) Vedlikehold en matrise eller liste for å beholde track av de besøkte nodene.
Trinn 3) Oppdater nodekostnaden med minimumskostnaden. Dette kan gjøres ved å sammenligne gjeldende kostnad med stikostnaden (demonstrert i eksempeldelen).
Trinn 4) Fortsett trinn 3 til alle nodene er besøkt.

Etter å ha fullført alle disse trinnene, vil vi finne stien som koster minimum fra kilde til destinasjon.

Forskjellen mellom Dijkstra og BFS, DFS

Hovedforskjellen mellom Dijkstra og BFS-DFS er at Dijkstra er en algoritme for å finne den korteste veien, mens BFS og DFS er generelle algoritmer for å finne veien. Generelt sett tar ikke BFS og DFS hensyn til kantkostnader når de finner veien. Så disse algoritmene kan ikke garantere den korteste veien.

2D-rutenettdemonstrasjon av hvordan BFS fungerer

Algoskisse, viser BFS-demonstrasjon

Denne demonstrasjonen indikerer at BFS bare finner banen. Den bryr seg imidlertid ikke om banens vekt. BFS (Bredde-først søk) antar at å reise fra en node til en annen node vil koste bare 1.

La oss se på et eksempel på en graf:

Her finner BFS en bane på nivå 2. BFS beveger seg gjennom grafen i nivårekkefølge. Så den beveger seg slik:

Trinn 1) Start fra node «1» og besøk alle tilstøtende noder 2, 3, 4.

Trinn 2) Marker nodene 2, 3, 4 som nivå 1 og besøk deres tilstøtende noder. Den vil fortsette å utforske alle tilstøtende noder til den når målnoden.

Når det gjelder DFS, vil den krysse banen fra 1 til 7 som følgende:

• 1→2→3→7 (opprinnelig kostnad 10, DFS-kostnad 3)
• 1→2→6→7 (opprinnelig kostnad 7, DFS-kostnad 3)
• 1→3→7 (opprinnelig kostnad 8, DFS-kostnad 2)
• 1→4→5→7 (opprinnelig kostnad 13, DFS-kostnad 3)

Som vi ser, beregner DFS sin banekostnad med antall kanter. DFS gjør følgende:

• DFS kan finne en vei fra kilden (startpunkt) til destinasjonen.
• Den kan ikke garantere om banen oppdaget fra kildenoden til destinasjonen er den korteste veien eller ikke.

Men når det gjelder Dijkstras algoritme, velger den kanter basert på kostnaden deres. Som en grådig algoritme vil den velge minimumskostnadsbanene.

Eksempel på Dijkstras algoritme

Dijkstras algoritme bruker kostnaden eller vekten for å beregne den totale kostnaden for banen.

Målet med Dijkstras algoritme er å minimere denne totale kostnaden eller vekten. I eksemplet vist ovenfor finner vi de beste veiene fra node 1 til node 7, og beregner deretter alle kostnadene.

I Dijkstras algoritme vil den finne de korteste stiene ved å beregne vekter. Den vil ikke søke etter alle mulige stier. La oss demonstrere Dijkstras algoritme med et eksempel. For eksempel, du har blitt bedt om å finne den korteste stien fra node 1 til 7.

For denne prosessen er trinnene gitt nedenfor:

Trinn 1) Initialiser startkostnaden for noden til 0. Tildel «Inf» til resten av nodene. Det betyr at det ikke finnes noen bane mellom kilden og noden, eller at banen ikke er besøkt ennå.

Trinn 2) Når du velger node 1, vil den bli merket som besøkt. Oppdater deretter alle tilstøtende naboer til node 1. 2, 3, 4 er nabonodene til node 1.

Når vi oppdaterer en kostnad, må vi følge prosedyren nedenfor:

Vi kan oppdatere kostnadene for hver node ved hjelp av formelen ovenfor. For eksempel var vi ved node 1, og vi måtte oppdatere kostnadene for de tilstøtende nodene 2, 3, 4. Etter oppdateringen vil kostnadene se slik ut:

Trinn 3) For node «2» er naboene 6 og 3. Vi oppdaterer kostnaden ved «6» ved å sammenligne uendelig (nåværende verdi) med kostnaden for node 2 + banekostnaden fra 2 til 6. Enkelt sagt vil node «6» ha kostnaden 1+3 eller 4.

Node 3 er nabo til node 2. Vi beregnet imidlertid kostnaden i forrige trinn, som var 7. Nå, hvis banen vår er 1-2-3, vil node 3 ha en kostnad på 10. Bane 1-2- 3 vil koste 10, mens 1 til 3 vil koste 7.

Trinn 4) For node 3 er nabonoden 7. Så, ved å sammenligne den nåværende verdien av node 7 med stikostnaden (7+1) eller 8, vil vi oppdatere kostnaden for node 7. Det er 8. Så vi finner en sti fra node 1 til node 7, og den er 1→3→7. Kostnaden er 8.

Trinn 5) For node 4 oppdaterer vi kostnaden for den tilstøtende noden deretter. Dermed vil node «5» ha en oppdatert kostnad på 8. Etter trinn 4 og 5 vil det se slik ut:

Nå har stien 1-3-7 en kostnad på 8 (tidligere). Node «7» ble ikke merket som besøkt fordi vi kan nå node «7» fra node «6». Stien «1-2-6» hadde en kostnad på 4. Så stien 1-2-6-7 vil ha en kostnad på 7.

Siden 7 < 8, vil den korteste veien fra kildepunkt «1» til destinasjonspunkt «7» være 1-2-6-7, og kostnaden er 7. Tidligere var den 1-3-7, og kostnaden var 8. Så den endelige grafen vil se slik ut:

Kanten merket med en svart strek er vår korteste vei fra 1 til 7, og den vil koste oss 7.

Kallenavn Code Dijkstras algoritme

Her er pseudokoden for Dijkstras algoritme:

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++ Implementering av Dijkstras algoritme

Å implementere Dijkstras algoritme ved hjelp av C++, her er koden:

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

Utgang:

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 Implementering av Dijkstras algoritme

Å implementere Dijkstras algoritme ved hjelp av Python, her er koden:

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)

Utgang:

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

Vi kan se at algoritmen beregner den korteste avstanden fra kildenoden.

Anvendelse av Dijkstra-algoritmen

Dijkstras algoritme har en rekke bruksområder. Blant disse er den mye brukt innen nettverksbygging. Her er noen praktiske bruksområder for Dijkstras algoritme:

Dijkstra i Google kart: Denne algoritmen er ryggraden for å finne de korteste stiene, som vi kan se fra kodestykket ovenfor.

Google bruker ikke den enkle Dijkstra-algoritmen. I stedet bruker den en modifisert versjon. Når du velger en destinasjon, viser den deg flere stier i Google Kart. Noen av disse stiene er sortert ut for brukeren. Disse stiene velges basert på «tid». Så «tid» er en kantkostnad for den korteste ruten.

Dijkstra i IP-ruting: IP-ruting er en nettverksterminologi. Den beskriver hvordan datapakken din sendes til mottakeren via forskjellige stier. Disse stiene består av rutere, servere og annet utstyr. I IP-ruting finnes det forskjellige typer protokoller.

Disse protokollene hjelper ruteren med å finne de korteste stiene for å sende dataene. Et av protokollnavnene er «OSPF (Open Shortest Path First)». OSPF bruker Dijkstras algoritme. Ruteren vedlikeholder en tabell over ruter. Hver ruter deler tabellen sin med naborutere. Etter å ha mottatt den oppdaterte tabellen, må de beregne alle stiene på nytt. På det tidspunktet bruker ruteren Dijkstras algoritme.

Begrensning av Dijkstras algoritme

Dijkstras algoritme kan ikke garantere den korteste veien i en graf med negative kanter. Dijkstras algoritme følger disse prinsippene:

• En korteste vei vil bli tatt fra en node til en annen.
• Når den korteste veien mellom to noder er valgt, vil den ikke bli beregnet igjen.

Legg her merke til to eksempler med negative kanter.

I den venstre grafen, Det er tre hjørner. Dijkstra vil kjøre på grafen slik:

Trinn 1) Startpunkt "1" vil bli initialisert til null. De andre nodene vil ha uendelig.

Trinn 2) Merk node «1» som besøkt og inkluder den i den korteste stien.

Trinn 3) Avstanden fra kildenode 1 til nodene «2» og «3» er satt til uendelig, ettersom den korteste veien ennå ikke er beregnet. Så enhver vei som koster mindre enn uendelig vil bli lagt til den korteste veien (grådig tilnærming).

Trinn 4) Oppdaterer avstanden fra kildenoden «1» til «2». Gjeldende vekt vil være 5 (5 < uendelig). På samme måte oppdaterer du avstanden fra node «1» til «3» med vekten 3.

Trinn 5) Hvis vi nå sjekker de korteste avstandene fra node «1», finner vi at 5 er den korteste avstanden for kant 1→2. Så node «2» vil bli merket som besøkt. På samme måte vil node «3» også bli merket som besøkt, ettersom den korteste avstanden er 3.

Hvis vi imidlertid observerer, finnes det en sti 1-3-2 som bare vil koste 2. Men Dijkstra viser at fra node «1» til node «2» er den korteste avstanden 5. Dijkstra klarte derfor ikke å beregne den korteste avstanden riktig. Årsaken er at Dijkstra er en grådig algoritme. Så når en node er merket som besøkt, vil den ikke bli vurdert på nytt, selv om det kan finnes en kortere sti tilgjengelig. Dette problemet oppstår bare når kantene har negative kostnader eller negative vektkanter.

Dijkstra klarer ikke å beregne den korteste veien mellom to noder i dette scenariet. Som et resultat har denne algoritmen noen ulemper. For å løse dette negative kantproblemet brukes en annen algoritme kalt «Bellman-Ford-algoritmen». Denne algoritmen kan fungere med negative kanter.

Dijkstras algoritmekompleksitet

Implementeringen ovenfor brukte to "for"-løkker. Disse løkkene kjører for antall toppunkter. Så tidskompleksiteten er O(V²)Her er begrepet «O» en notasjon som gir en antagelse for Dijkstra-algoritmen.

Vi kan lagre grafen ved hjelp av en «prioritetskø». En prioritetskø er en binær heap-datastruktur. Den vil være mer effektiv enn en 2D-matrise. En kant med minimal kostnad vil ha høy prioritet. Da vil tidskompleksiteten være O(E log V). Her er E antall kanter, og V er antall topper.

Romkompleksiteten er O(V²), da vi bruker en tilstøtende matrise (2D-array). Plasskompleksitet kan optimaliseres ved hjelp av en tilstøtende liste eller kødatastruktur.

Spørsmål og svar