Dijkstras algoritme i Python & C++ (Eksempel)

Hvad er den korteste vej eller korteste afstand?

En sti fra kildehjørnet til destinationshjørnet, der koster et minimum, er den korteste sti eller korteste afstand. I grafteori er det muligt at have flere ruter fra en kilde til en destination. Blandt disse ruter, hvis der er en rute, der koster et minimumsbeløb, kalder vi den den korteste sti.

Her betyder "omkostninger" antallet af noder i ruten eller summen af ​​omkostninger på hver kant. En sti kan have en eller flere kanter. Forbindelsen mellem to hjørner kaldes en "kant". Der findes forskellige typer af korteste-sti-algoritmer, såsom Dijkstras algoritme og Bellman-Ford-algoritmen.

Her diskuterer vi Dijkstras algoritme. Lad os se på følgende vægtede graf:

En urettet-vægtet graf

• Udtrykket "vægtet" betyder omkostningerne ved at flytte fra en node til en anden. For eksempel, hvis man flytter fra node 1 til node 2, er omkostningerne eller vægten 1.
• Stien mellem node 1 og node 2 kaldes kanten.
• "Udirigeret" betyder, at du kan bevæge dig fra en node til en anden og tilbage til den forrige node. Så hvis vi prøver at finde alle ruterne fra node 1 til node 7, vil de være:

Blandt disse fire ruter kan vi se, at den første rute koster 7. Så det er den korteste vej med hensyn til omkostninger.

Korteste sti

Sådan fungerer Dijkstras algoritme

Dijkstras algoritme kan finde den korteste afstand i både rettede og ikke-rettede vægtede grafer. Denne algoritme er grådig, fordi den altid vælger den korteste eller nærmeste knude fra origo. Udtrykket "grådig" betyder, at algoritmen vil vælge det bedste blandt et sæt af udfald eller resultater.

Her forsøger vi at finde de korteste stier blandt alle andre ruter. Dijkstras algoritme finder derfor alle de korteste stier fra en enkelt kildenode. Som et resultat opfører den sig som en grådig algoritme.

I afsnittet "eksempel" nedenfor kan du se den trinvise fremgangsmåde. Den fungerer som følger:

Trin 1) Initialiser startnoden med omkostninger på 0 og resten af ​​noderne med uendelig pris.
Trin 2) Vedligehold et array eller en liste for at bevare track af de besøgte noder.
Trin 3) Opdater nodeomkostningerne med minimumsomkostningen. Dette kan gøres ved at sammenligne de aktuelle omkostninger med stiomkostningerne (demonstreret i eksempelafsnittet).
Trin 4) Fortsæt trin 3, indtil alle noder er besøgt.

Efter at have gennemført alle disse trin, vil vi finde stien, der koster et minimum fra kilde til destination.

Forskellen mellem Dijkstra og BFS, DFS

Hovedforskellen mellem Dijkstra og BFS-DFS er, at Dijkstra er en algoritme til at finde den korteste sti, mens BFS og DFS er generelle algoritmer til at finde sti. Generelt tager BFS og DFS ikke højde for kantomkostninger, når de finder stien. Så disse algoritmer kan ikke garantere den korteste sti.

2D-gitterdemonstration af, hvordan BFS fungerer

Algosketch, der viser BFS-demonstration

Denne demonstration indikerer, at BFS kun finder stien. Den er dog ligeglad med stiens vægt. BFS (Bredde-første søgning) antager, at det kun vil koste 1 at rejse fra en node til en anden.

Lad os se et eksempel på en graf:

Her finder BFS en sti på niveau 2. BFS bevæger sig hen over grafen i niveauorden. Den bevæger sig således:

Trin 1) Start fra knudepunkt “1” og besøg alle de tilstødende knudepunkter 2, 3, 4.

Trin 2) Marker knudepunkterne 2, 3, 4 som niveau 1, og besøg deres tilstødende knudepunkter. Den vil fortsætte med at udforske alle tilstødende knudepunkter, indtil den når destinationsnoden.

Med hensyn til DFS vil den krydse stien fra 1 til 7 som følgende:

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

Som vi ser, beregner DFS sine stiomkostninger med antallet af kanter. DFS gør følgende:

• DFS kan finde en sti fra kilde (startpunkt) til destination.
• Den kan ikke garantere, om den opdagede sti fra kildenoden til destinationen er den korteste sti eller ej.

Men ifølge Dijkstras algoritme vælger den kanter baseret på deres omkostninger. Som en grådig algoritme vil den vælge de minimale omkostningsstier.

Eksempel på Dijkstras algoritme

Dijkstras algoritme bruger omkostningerne eller vægten til at beregne de samlede omkostninger for stien.

Målet med Dijkstras algoritme er at minimere disse samlede omkostninger eller vægt. I eksemplet vist ovenfor finder vi de bedste veje fra node 1 til node 7, og beregner derefter alle omkostningerne.

I Dijkstras algoritme finder den de korteste stier ved at beregne vægte. Den søger ikke efter alle mulige stier. Lad os demonstrere Dijkstras algoritme med et eksempel. For eksempel er du blevet bedt om at finde den korteste sti fra node 1 til 7.

Til denne proces er trin angivet nedenfor:

Trin 1) Initialiser startnodeomkostningerne til 0. Tildel "Inf" til resten af ​​noderne. Det betyder, at der ikke findes nogen sti mellem kilden og noden, eller at stien endnu ikke er besøgt.

Trin 2) Når du vælger node 1, markeres den som besøgt. Opdater derefter alle tilstødende naboer til node 1. 2, 3, 4 er naboknoder til node 1.

Når vi opdaterer en pris, skal vi følge nedenstående procedure:

Vi kan opdatere hver nodes omkostninger ved hjælp af ovenstående formel. For eksempel var vi ved node 1, og vi skulle opdatere omkostningerne for de tilstødende noder 2, 3, 4. Efter opdateringen vil omkostningerne se sådan ud:

Trin 3) For node "2" er naboerne 6 og 3. Vi opdaterer omkostningerne ved "6" ved at sammenligne uendelighed (aktuel værdi) med omkostningerne for node 2 + stiomkostninger fra 2 til 6. Kort sagt vil node "6" have omkostningerne 1+3 eller 4.

Node 3 er nabo til node 2. Men vi beregnede dens pris i det foregående trin, som var 7. Hvis vores vej nu er 1-2-3, vil node 3 have en pris på 10. Sti 1-2- 3 koster 10, mens 1 til 3 koster 7.

Trin 4) For node 3 er den nærliggende node 7. Så hvis vi sammenligner den aktuelle værdi af node 7 med stiomkostningerne (7+1) eller 8, opdaterer vi omkostningerne for node 7. Det er 8. Så vi finder en sti fra node 1 til node 7, og den er 1→3→7. Omkostningerne er 8.

Trin 5) For node 4 opdaterer vi prisen for den tilstødende node i overensstemmelse hermed. Så node "5" vil have en opdateret pris på 8. Efter trin 4 og 5 vil det se sådan ud:

Stien 1-3-7 har nu en pris på 8 (tidligere). Knudepunkt "7" var ikke markeret som besøgt, fordi vi kan nå knudepunkt "7" fra knudepunkt "6". Stien "1-2-6" havde en pris på 4. Så stien 1-2-6-7 vil have en pris på 7.

Da 7 < 8, vil den korteste vej fra kildepunkt "1" til destinationspunkt "7" være 1-2-6-7, og omkostningerne er 7. Tidligere var den 1-3-7, og omkostningerne var 8. Så den endelige graf vil se sådan ud:

Kanten markeret med en sort streg er vores korteste vej fra 1 til 7, og det vil koste os 7.

Kaldenavn Code Dijkstras algoritme

Her er pseudokoden til 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 af Dijkstras algoritme

At implementere Dijkstras algoritme vha 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);
}

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

At implementere Dijkstras algoritme vha 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)

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

Vi kan se, at algoritmen beregner den korteste afstand fra kildenoden.

Anvendelse af Dijkstra Algorithm

Dijkstras algoritme har et bredt sæt anvendelser. Blandt disse er den meget udbredt inden for netværk. Her er nogle praktiske anvendelser af Dijkstras algoritme:

Dijkstra i Google Kort: Denne algoritme er rygraden i at finde de korteste stier, som vi kan se af kodestykket ovenfor.

Google bruger ikke den simple Dijkstra-algoritme. I stedet bruger den en modificeret version. Når du vælger en destination, viser den dig flere stier i Google Kort. Blandt disse stier er nogle sorteret ud for brugeren. Disse stier er udvalgt baseret på "tid". Så "tid" er en kantomkostning for den korteste sti.

Dijkstra i IP-routing: IP routing er en netværksterminologi. Den beskriver, hvordan din datapakke sendes til modtageren via forskellige stier. Disse stier består af routere, servere og andet udstyr. I IP-routing findes der forskellige typer protokoller.

Disse protokoller hjælper routeren med at finde de korteste stier at sende dataene til. Et af protokolnavnene er "OSPF (Open Shortest Path First)". OSPF bruger Dijkstras algoritme. Routeren vedligeholder en tabel over ruter. Hver router deler sin tabel med naboroutere. Efter at have modtaget den opdaterede tabel skal de beregne alle stierne igen. På det tidspunkt bruger routeren Dijkstras algoritme.

Begrænsning af Dijkstras algoritme

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

• En korteste vej vil blive taget fra en knude til en anden.
• Når den korteste vej mellem to noder er valgt, vil den ikke blive beregnet igen.

Læg her mærke til to eksempler med negative kanter.

I den venstre graf, Der er tre hjørner. Dijkstra vil køre på grafen som følger:

Trin 1) Startpunkt "1" vil blive initialiseret til nul. De andre noder vil have uendelighed.

Trin 2) Marker node “1” som besøgt, og inkluder den i den korteste sti.

Trin 3) Afstanden fra kildenode 1 til noderne "2" og "3" er sat til uendelig, da den korteste vej endnu ikke er beregnet. Så enhver vej, der koster mindre end uendelig, vil blive lagt til den korteste vej (grådig tilgang).

Trin 4) Opdaterer afstanden fra kildepunkt "1" til "2". Den nuværende vægt vil være 5 (5 < uendelighed). Opdater ligeledes afstanden fra knudepunkt "1" til "3" med vægten 3.

Trin 5) Hvis vi nu tjekker de korteste afstande fra knudepunkt "1", finder vi, at 5 er den korteste afstand for kant 1→2. Så knudepunkt "2" vil blive markeret som besøgt. Tilsvarende vil knudepunkt "3" også blive markeret som besøgt, da den korteste afstand er 3.

Hvis vi observerer det, er der en sti 1-3-2, der kun koster 2. Men Dijkstra viser, at fra node "1" til node "2" er den korteste afstand 5. Dijkstra beregnede derfor ikke den korteste afstand korrekt. Årsagen er, at Dijkstra er en grådig algoritme. Så når en node er markeret som besøgt, vil den ikke blive genovervejet, selvom der muligvis er en kortere sti tilgængelig. Dette problem opstår kun, når kanterne har negative omkostninger eller negative vægtflanker.

Dijkstra undlader at beregne den korteste vej mellem to noder i dette scenarie. Som følge heraf har denne algoritme nogle ulemper. For at løse dette negative kantproblem anvendes en anden algoritme kaldet "Bellman-Ford-algoritmen". Denne algoritme kan arbejde med negative kanter.

Dijkstras algoritmekompleksitet

Implementeringen ovenfor brugte to "for"-løkker. Disse sløjfer kører for antallet af hjørner. Så tidskompleksiteten er O(V²)Her er udtrykket "O" en notation, der giver en antagelse for Dijkstra-algoritmen.

Vi kan gemme grafen ved hjælp af en "prioritetskø". En prioritetskø er en binær heap-datastruktur. Den vil være mere effektiv end en 2D-matrix. En kant med minimale omkostninger vil have en høj prioritet. Så vil tidskompleksiteten være O(E log V). Her er E antallet af kanter, og V er antallet af hjørner.

Rumkompleksiteten er O(V²), da vi bruger en adjacency matrix (2D-array). Pladskompleksitet kan optimeres ved hjælp af en tilstødende liste eller kødatastruktur.

Ofte Stillede Spørgsmål