Dijsktras algoritm: C++, Python Kodsexempel
Sarah Chen
Vilken är den kortaste vägen eller den kortaste sträckan?
En väg från källpunkten till destinationspunkten som kostar ett minimum är den kortaste vägen eller det kortaste avståndet. I grafteorin är det möjligt att ha flera rutter från en källa till en destination. Mellan dessa rutter, om det finns en rutt som kostar ett minimibelopp, kan vi kalla det den kortaste vägsalgoritmen.
Här betyder "Kostnad" antalet noder i rutten eller summan av kostnader på varje väg. En bana kan ha en eller flera kanter. Kopplingen mellan två hörn kallas "kant". Det finns olika typer av algoritmer för kortaste vägen, som Dijkstras algoritm, Bellman-Ford-algoritm, etc.
Här diskuterar vi om Dijkstras algoritm
Låt oss titta på följande viktade graf:
- Termen "vägd" betyder att flytta kostnader från en nod till en annan. Om du till exempel flyttar från nod 1 till nod 2 är kostnaden eller vikten 1.
- Vägen mellan nod 1 till nod 2 kallas kanten.
- "Oriktad" betyder att du kan flytta 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, så blir det:
| Rutt eller stig | Pris |
|---|---|
| 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 |
Bland dessa fyra rutter kan vi se att den första sträckan kommer att kosta oss 7. Så det är den kortaste vägen sett till kostnad.
Hur Dijkstras algoritm fungerar
Dijkstra-algoritmen 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 ursprunget. Termen "girig" betyder att bland en uppsättning resultat 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 vägar. Så Dijkstras algoritm hittar alla de kortaste vägarna från en enda destinationsnod. Som ett resultat beter den sig som en girig algoritm.
I avsnittet "exempel" nedan ser du steg-för-steg-metoden. Det fungerar enligt följande:
Steg 1) Initiera startnoden med 0 kostnader och resten av noden som Infinity Cost.
Steg 2) Underhåll en array eller lista för att hålla reda på de besökta noderna
Steg 3) Uppdatera nodkostnaden med lägsta kostnad. Det kan göras genom att jämföra den aktuella kostnaden med vägkostnaden. (Demonstrationen 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 huvudsakliga skillnaden mellan Dijkstra och BFS-DFS är att Dijkstra är den kortaste vägsökningsalgoritmen och BFS, DFS är vägsökningsalgoritmen. I vanliga fall tar BFS och DFS inte hänsyn till kostnaden när de hittar vägen. Så dessa algoritmer kan inte garantera den kortaste vägen.
2D-rutnätsdemonstration av hur BFS fungerar
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.
Men låt oss se en exempelgraf:
Här hittar den en väg i nivå 2. BFS korsar grafen i nivåordning. Så den färdas så här:
Steg 1) Börja från nod "1" och besök alla intilliggande noder 2,3,4
Steg 2) Markera nod 2,3,4 som nivå 1 och besök deras närliggande noder. Den kommer att fortsätta att utforska alla intilliggande 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 djup eller antal 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 när det gäller Dijkstra-algoritmen kommer den att välja kanter baserat på deras kostnad. Som en girig algoritm kommer den att välja de bästa eller 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. Det kommer inte att söka efter alla möjliga vägar. Låt oss demonstrera Dijkstras algoritm med ett exempel. Du har till exempel blivit ombedd att hitta den kortaste vägen från nod 1 till 7.
För denna process ges stegen nedan:
Steg 1) Initiera startnodkostnaden till 0.
Resten av noden, tilldela "Inf". Det betyder att det inte finns någon väg mellan startpunkten (källan) och noden, eller så har sökvägen inte besökts ännu.
Steg 2) När du väljer nod 1 kommer den att markeras som besökt. Uppdatera sedan alla angränsande grannar till nod 1. 2,3,4 är angränsande noder till nod 1.
När vi uppdaterar en kostnad måste vi följa proceduren nedan:
Vi kan uppdatera varje nods kostnad genom att använda formeln ovan. Till exempel var vi vid nod 1, och vi behövde uppdatera kostnaden för dess närliggande nod 2,3,4.
Efter uppdateringen kommer kostnaden eller vikten att se ut så här:
Steg 3) För nod "2", grannar är 6 och 3. Vi uppdaterar kostnaden till "6" genom att jämföra oändlighet (aktuellt värde). Kostnaden för nod 2 + vägkostnad från 2 till 6. Säg helt enkelt, nod "6" kommer 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, närliggande nod är 7. Så, om vi jämför det nuvarande 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, vi kommer att uppdatera dess närliggande nodkostnad i enlighet med detta. Så nod "5" kommer att ha en uppdaterad kostnad på 8. Efter steg 4,5 kommer det att se ut så här:
Nu har vägen 1-3-7 kostnaden för 8 (tidigare). Nod "7" markerades inte som besökt eftersom vi kan nå nod "7" från nod "6". Vägen "1-2-6" hade en kostnad på 4. Så vägen 1-2-6-7 kommer att kosta 7.
Eftersom 7 < 8 är det därför den kortaste vägen från källpunkt "1" till destinationspunkt "7" kommer att vara 1-2-6-7, och kostnaden är 7. Tidigare var den 1-3-7, och kostnaden var 8.
Så, den sista 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.
Pseudokod Dijkstras algoritm
Här är pseudokoden för Dijkstras algoritm
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++ 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] & 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);
}
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 pytonorm, 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] & 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)
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
Dijkstra Algo har en stor uppsättning användningsområden. Bland dessa används det i stor utsträckning inom nätverksområdet. Här är några av den verkliga användningen av Dijkstras algoritm:
Dijkstra på Google karta: I grund och botten är denna algoritm ryggraden för att hitta de kortaste vägarna. Som vi kan se från ovanstående kodavsnitt.
Google använder inte den enkla Dijkstra-algoritmen. Istället använder den en modifierad version. När du väljer en destination visar den dig flera vägar i Google Map. Bland dessa sökvägar sorteras vissa vägar ut för användaren. Dessa vägar som väljs är baserade på "tiden". Så "tid" är en kantkostnad för den kortaste vägen.
Dijkstra i IP-routing: IP routing är en nätverksterminologi. Det betyder hur ditt datapaket skickas till mottagaren via olika vägar. Dessa vägar består av routrar, servrar etc. 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 dijkstra-algoritmen. Routern upprätthåller en tabell över rutter. Varje router delar sin tabell med grannroutrar. Efter att ha fått den uppdaterade tabellen måste de beräkna alla vägar igen. Vid den tiden använder routern Dijkstra-algoritmen.
Begränsning av Dijkstras algoritm
Dijkstra-algoritmen kan inte garantera den kortaste vägen i grafen med negativ kant. Dijkstra-algoritmen följer dessa metoder:
- 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 hörn. Dijkstra kommer att köra på grafen enligt följande:
Steg 1) Startpunkt "1" initieras till noll. De andra noderna kommer att ha oändlighet.
Steg 2) Markera nod "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 inställt på oändligt, eftersom den kortaste vägen ännu inte har beräknats. Så alla vägar som kommer att kosta mindre än oändligt kommer att läggas till den kortaste vägen (giriga tillvägagångssätt).
Steg 4) Uppdatering av avståndet från källpunkten eller källnoden "1" till "2". Den aktuella vikten kommer att vara 5 (5
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å samma sätt kommer nod "3" också att markeras som besökt eftersom det kortaste avståndet är 3.
Men om vi observerar finns det en väg 1-3-2 som bara kommer att kosta 2. Men Dijkstra visar att från nod "1" till nod "2" är det kortaste avståndet 5. Så Dijkstra misslyckades med att beräkna det kortaste avståndet korrekt. Anledningen till att det hände ä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. Det här problemet uppstår endast 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 några nackdelar. För att lösa detta negativa kantproblem används en annan algoritm som kallas "Bellman-Ford Algorithm". Den algoritmen kan fungera 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(V2). Här betyder termen "0" en notation som ger ett antagande för Dijkstra-algoritmen.
Vi kan lagra grafen med "Prioritetskö". En prioritetskö är en binär högdatastruktur. Det kommer att vara mer effektivt än en 2D-matris. En kant som kommer att ha en lägsta kostnad kommer att ha hög prioritet.
Då blir tidskomplexiteten O (E log (V)). Här är E antalet kanter och V är antalet hörn.
Utrymmets komplexitet är O(V2), eftersom vi använder en närliggande matris (2D-array). Utrymmeskomplexitet kan optimeras med hjälp av en angränsande lista eller ködatastruktur.
