Dijkstras algoritm i Python & C++ (Exempel)

Vad är den kortaste vägen eller kortaste avståndet?

En väg från källnoden till destinationsnoden som kostar ett minimum är den kortaste vägen eller det kortaste avståndet. Inom grafteori är det möjligt att ha flera rutter från en källa till en destination. Bland dessa rutter, om det finns en rutt som kostar ett minimum, kallar vi den den kortaste vägen.

Här betyder "kostnad" antalet noder i rutten eller summan av kostnaderna på varje kant. En väg kan ha en eller flera kanter. Förbindelsen mellan två noder kallas en "kant". Det finns olika typer av algoritmer för kortaste vägen, såsom Dijkstras algoritm och Bellman-Ford-algoritmen.

Här diskuterar vi Dijkstras algoritm. Låt oss titta på följande viktade graf:

En oriktad-viktad graf

• Termen "viktad" betyder kostnaden för att flytta från en nod till en annan. Till exempel, om man flyttar från nod 1 till nod 2, är kostnaden eller vikten 1.
• Vägen mellan nod 1 och nod 2 kallas kanten.
• ”Oriktad” betyder att du kan förflytta dig från en nod till en annan och tillbaka till föregående nod. Så om vi försöker hitta alla rutter från nod 1 till nod 7, kommer de att vara:

Bland dessa fyra rutter kan vi se att den första rutten kostar 7. Så det är den kortaste vägen kostnadsmässigt.

Kortaste vägen

Hur Dijkstras algoritm fungerar

Dijkstras algoritm kan hitta det kortaste avståndet i både riktade och oriktade viktade grafer. Denna algoritm är girig eftersom den alltid väljer den kortaste eller närmaste noden från origo. Termen "girig" betyder att bland en uppsättning utfall eller resultat kommer algoritmen att välja det bästa av dem.

Här försöker vi hitta de kortaste vägarna bland alla andra rutter. Så Dijkstras algoritm hittar alla kortaste vägar från en enda källnod. Som ett resultat beter sig den som en girig algoritm.

I avsnittet "exempel" nedan ser du steg-för-steg-metoden. Det fungerar så här:

Steg 1) Initiera startnoden med kostnad 0 och resten av noderna med oändlig kostnad.
Steg 2) Underhåll en array eller lista för att behålla track av de besökta noderna.
Steg 3) Uppdatera nodkostnaden med minimikostnaden. Det kan göras genom att jämföra den aktuella kostnaden med vägkostnaden (visas i exempelavsnittet).
Steg 4) Fortsätt steg 3 tills alla noder har besökts.

Efter att ha genomfört alla dessa steg kommer vi att hitta vägen som kostar minst från källa till destination.

Skillnaden mellan Dijkstra och BFS, DFS

Den största skillnaden mellan Dijkstra och BFS-DFS är att Dijkstra är en algoritm för att hitta den kortaste vägen, medan BFS och DFS är generella algoritmer för att hitta vägen. I allmänhet tar BFS och DFS inte hänsyn till kantkostnader när de hittar vägen. Så dessa algoritmer kan inte garantera den kortaste vägen.

2D-rutnätsdemonstration av hur BFS fungerar

Algosketch, som visar BFS-demonstration

Denna demonstration indikerar att BFS bara hittar vägen. Den bryr sig dock inte om stigens vikt. BFS (Utöka första sökningen) antar att resa från en nod till en annan nod endast kommer att kosta 1.

Låt oss se ett exempeldiagram:

Här hittar BFS en bana på nivå 2. BFS passerar grafen i nivåordning. Så den rör sig så här:

Steg 1) Börja från nod "1" och besök alla intilliggande noder 2, 3, 4.

Steg 2) Markera noderna 2, 3, 4 som nivå 1 och besök deras angränsande noder. Den fortsätter att utforska alla angränsande noder tills den når destinationsnoden.

När det gäller DFS kommer den att korsa vägen från 1 till 7 som följande:

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

Som vi ser beräknar DFS sin vägkostnad med antalet kanter. DFS gör följande:

• DFS kan hitta en väg från källa (startpunkt) till destination.
• Det kan inte garantera om sökvägen som upptäckts från källnod till destination är den kortaste vägen eller inte.

Men enligt Dijkstras algoritm väljer den kanter baserat på deras kostnad. Som en girig algoritm kommer den att välja de lägsta kostnadsvägarna.

Exempel på Dijkstras algoritm

Dijkstras algoritm använder kostnaden eller vikten för att beräkna den totala kostnaden för vägen.

Målet med Dijkstras algoritm är att minimera denna totala kostnad eller vikt. I exemplet som visas ovan hittar vi de bästa vägarna från nod 1 till nod 7, och beräknar sedan alla kostnader.

I Dijkstras algoritm hittar den de kortaste vägarna genom att beräkna vikter. Den söker inte efter alla möjliga vägar. Låt oss demonstrera Dijkstras algoritm med ett exempel. Till exempel har du blivit ombedd att hitta den kortaste vägen från nod 1 till 7.

För denna process ges stegen nedan:

Steg 1) Initiera startkostnaden för noden till 0. Tilldela "Inf" till resten av noderna. Det betyder att det inte finns någon sökväg mellan källan och noden, eller att sökvägen ännu inte har besökts.

Steg 2) När du väljer nod 1 markeras den som besökt. Uppdatera sedan alla angränsande grannar till nod 1. 2, 3, 4 är grannoderna till nod 1.

När vi uppdaterar en kostnad måste vi följa proceduren nedan:

Vi kan uppdatera varje nods kostnad med hjälp av formeln ovan. Till exempel var vi vid nod 1 och behövde uppdatera kostnaden för dess angränsande noder 2, 3, 4. Efter uppdateringen kommer kostnaderna att se ut så här:

Steg 3) För nod "2" är grannarna 6 och 3. Vi uppdaterar kostnaden vid "6" genom att jämföra oändligheten (nuvarande värde) med kostnaden för nod 2 + vägkostnaden från 2 till 6. Enkelt uttryckt kommer nod "6" att ha kostnaden 1+3 eller 4.

Nod 3 är granne till nod 2. Vi beräknade dock dess kostnad i föregående steg, som var 7. Nu, om vår väg är 1-2-3, kommer nod 3 att ha en kostnad på 10. Väg 1-2- 3 kommer att kosta 10, medan 1 till 3 kommer att kosta 7.

Steg 4) För nod 3 är den angränsande noden 7. Så, om vi jämför det aktuella värdet för nod 7 med vägkostnaden (7+1) eller 8, kommer vi att uppdatera kostnaden för nod 7. Det är 8. Så vi hittar en väg från nod 1 till nod 7, och den är 1→3→7. Kostnaden är 8.

Steg 5) För nod 4 kommer vi att uppdatera kostnaden för dess angränsande nod i enlighet därmed. Så nod "5" kommer att ha en uppdaterad kostnad på 8. Efter steg 4 och 5 kommer det att se ut så här:

Nu har vägen 1-3-7 kostnaden 8 (tidigare). Noden "7" markerades inte som besökt eftersom vi kan nå noden "7" från noden "6". Vägen "1-2-6" hade en kostnad på 4. Så vägen 1-2-6-7 kommer att ha en kostnad på 7.

Eftersom 7 < 8, kommer den kortaste vägen från källnoden "1" till destinationsnoden "7" att vara 1-2-6-7, och kostnaden är 7. Tidigare var den 1-3-7, och kostnaden var 8. Så den slutliga grafen kommer att se ut så här:

Kanten markerad med en svart linje är vår kortaste väg från 1 till 7, och det kommer att kosta oss 7.

Pseudo Code Dijkstras algoritm

Här är pseudokoden för Dijkstras algoritm:

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 algoritm

Att implementera Dijkstras algoritm med hjälp av C++, här är 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);
}

Produktion:

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 algoritm

Att implementera Dijkstras algoritm med hjälp av Python, här är 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)

Produktion:

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 att algoritmen beräknar det kortaste avståndet från källnoden.

Tillämpning av Dijkstra Algorithm

Dijkstras algoritm har en mängd olika användningsområden. Bland dessa används den flitigt inom nätverksteknik. Här är några verkliga användningsområden för Dijkstras algoritm:

Dijkstra i Google Kartor: Denna algoritm är ryggraden för att hitta de kortaste vägarna, som vi kan se av kodavsnittet ovan.

Google använder inte den enkla Dijkstra-algoritmen. Istället använder den en modifierad version. När du väljer en destination visas flera sökvägar i Google Kartor. Bland dessa vägar sorteras några ut för användaren. Dessa vägar väljs ut baserat på "tid". Så "tid" är en kantkostnad för den kortaste vägen.

Dijkstra i IP-routing: IP routing är en nätverksterminologi. Den beskriver hur ditt datapaket skickas till mottagaren via olika vägar. Dessa vägar består av routrar, servrar och annan utrustning. Inom IP-routing finns det olika typer av protokoll.

Dessa protokoll hjälper routern att hitta de kortaste vägarna för att skicka data. Ett av protokollnamnen är "OSPF (Open Shortest Path First)". OSPF använder Dijkstras algoritm. Routern upprätthåller en tabell över rutter. Varje router delar sin tabell med grannroutrar. Efter att ha mottagit den uppdaterade tabellen måste de beräkna alla vägar igen. Vid den tidpunkten använder routern Dijkstras algoritm.

Begränsning av Dijkstras algoritm

Dijkstras algoritm kan inte garantera den kortaste vägen i en graf med negativa kanter. Dijkstras algoritm följer dessa principer:

• En kortaste väg kommer att tas från en nod till en annan.
• När den kortaste vägen mellan två noder har valts kommer den inte att beräknas igen.

Lägg märke till två exempel med negativa kanter.

I den vänstra grafen, Det finns tre noder. Dijkstra kommer att köras på grafen så här:

Steg 1) Startpunkt "1" initieras till noll. De andra noderna kommer att ha oändlighet.

Steg 2) Markera noden "1" som besökt och inkludera den i den kortaste vägen.

Steg 3) Avståndet från källnod 1 till noderna "2" och "3" är satt till oändligheten, eftersom den kortaste vägen ännu inte har beräknats. Så varje väg som kostar mindre än oändligheten kommer att läggas till den kortaste vägen (girig metod).

Steg 4) Uppdaterar avståndet från källnoden "1" till "2". Den aktuella vikten blir 5 (5 < oändligheten). Uppdatera på liknande sätt avståndet från noden "1" till "3" med vikten 3.

Steg 5) Om vi ​​nu kontrollerar de kortaste avstånden från nod "1", finner vi att 5 är det kortaste avståndet för kant 1→2. Så nod "2" kommer att markeras som besökt. På liknande sätt kommer nod "3" också att markeras som besökt eftersom det kortaste avståndet är 3.

Om vi ​​emellertid observerar det finns en väg 1-3-2 som bara kostar 2. Men Dijkstra visar att från nod "1" till nod "2" är det kortaste avståndet 5. Dijkstra misslyckades alltså med att beräkna det kortaste avståndet korrekt. Anledningen är att Dijkstra är en girig algoritm. Så när en nod väl är markerad som besökt kommer den inte att omprövas, även om det kan finnas en kortare väg tillgänglig. Detta problem uppstår bara när kanterna har negativa kostnader eller negativa viktkanter.

Dijkstra misslyckas med att beräkna den kortaste vägen mellan två noder i detta scenario. Som ett resultat har denna algoritm vissa nackdelar. För att lösa detta negativa kantproblem används en annan algoritm som kallas "Bellman-Ford-algoritmen". Den algoritmen kan arbeta med negativa kanter.

Dijkstras algoritmkomplexitet

Implementeringen ovan använde två "för"-loopar. Dessa slingor löper för antalet hörn. Så, tidskomplexiteten är O(V²)Här är termen "O" en notation som ger ett antagande för Dijkstra-algoritmen.

Vi kan lagra grafen med hjälp av en "prioritetskö". En prioritetskö är en binär heap-datastruktur. Den kommer att vara mer effektiv än en 2D-matris. En kant med minimal kostnad kommer att ha hög prioritet. Då kommer tidskomplexiteten att vara O(E log V). Här är E antalet kanter och V är antalet hörn.

Utrymmets komplexitet är O(V²), eftersom vi använder en närliggande matris (2D-array). Utrymmeskomplexitet kan optimeras med hjälp av en angränsande lista eller ködatastruktur.

Vanliga frågor