Dijsktras algoritme: C++, Python Kodeeksempel
Sarah Chen
Hvad er den korteste vej eller den korteste afstand?
En sti fra kildehjørnet til destinationspunktet, 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. Mellem disse ruter, hvis der er en rute, der koster et minimumsbeløb, kan vi kalde det den korteste vejs algoritme.
Her betyder "omkostninger" antallet af knudepunkter i ruten eller summeringen af omkostninger på hver sti. En sti kan have en eller flere kanter. Forbindelsen mellem to hjørner kaldes "kant". Der er forskellige typer af korteste vejs algoritmer, såsom Dijkstras algoritme, Bellman-Ford algoritme osv.
Her diskuterer vi om Dijkstras algoritme
Lad os se på følgende vægtede graf:
- Udtrykket "Vægtet" betyder at flytte omkostninger fra en knude til en anden. Hvis du for eksempel flytter fra node 1 til node 2, er prisen eller vægten 1.
- Stien mellem node 1 til node 2 kaldes kanten.
- "Udirigeret" betyder, at du kan flytte 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, så bliver det:
| Rute eller sti | Koste |
|---|---|
| 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 |
Blandt disse fire ruter kan vi se, at den første rute vil koste os 7. Så det er den korteste vej med hensyn til omkostninger.
Sådan fungerer Dijkstras algoritme
Dijkstra-algoritmen kan finde den korteste afstand i både rettede og urettede vægtede grafer. Denne algoritme er grådig, fordi den altid vælger den korteste eller nærmeste knude fra oprindelsen. Udtrykket "grådig" betyder, at blandt et sæt af resultater eller resultater vil algoritmen vælge det bedste af dem.
Her forsøger vi at finde de korteste veje blandt alle andre ruter. Så Dijkstras algoritme finder alle de korteste veje fra en enkelt destinationsknude. Som et resultat opfører den sig som en grådig algoritme.
I afsnittet "eksempel" nedenfor kan du se trin-for-trin tilgangen. Det fungerer som følger:
Trin 1) Initialiser startknuden med 0 omkostninger og resten af knudepunktet som Infinity Cost.
Trin 2) Vedligehold et array eller en liste for at holde styr på de besøgte noder
Trin 3) Opdater nodeomkostningerne med minimumsomkostningerne. Det kan gøres ved at sammenligne den aktuelle omkostning med stiomkostningen. (Demonstration er vist i eksempelsektionen)
Trin 4) Fortsæt trin 3, indtil hele knudepunktet 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
Den største forskel mellem Dijkstra og BFS-DFS er, at Dijkstra er den korteste stifindingsalgoritme, og BFS, DFS er stifindingsalgoritmen. I generelle tilfælde tager BFS og DFS ikke omkostningerne i betragtning, mens de finder stien. Så disse algoritmer kan ikke garantere den korteste vej.
2D grid demonstration af, hvordan BFS fungerer
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.
Men lad os se en eksempelgraf:
Her finder den en sti i niveau 2. BFS krydser grafen i niveaurækkefølge. Så det rejser som:
Trin 1) Start fra node "1" og besøg alle de tilstødende noder 2,3,4
Trin 2) Marker node 2,3,4 som niveau 1 og besøg deres tilstødende noder. Den vil fortsætte med at udforske alle de tilstødende noder, indtil den når destinationsknuden.
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 sin vejomkostninger med antallet af dybder eller 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 med hensyn til Dijkstra-algoritmen vil den vælge kanter baseret på deres omkostninger. Som en grådig algoritme vil den vælge de bedste eller laveste omkostninger.
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 vil den finde de korteste veje ved at beregne vægte. Den vil ikke søge efter alle mulige veje. Lad os demonstrere Dijkstras algoritme med et eksempel. For eksempel er du blevet bedt om at finde den korteste vej fra node 1 til 7.
Til denne proces er trin angivet nedenfor:
Trin 1) Initialiser startknudeomkostningerne til 0.
Resten af noden, tildel "Inf". Det betyder, at der ikke eksisterer nogen sti mellem startpunktet (kilden) og knudepunktet, eller stien er ikke besøgt endnu.
Trin 2) Når du vælger node 1, vil den blive markeret som besøgt. Opdater derefter alle de tilstødende naboer til node 1. 2,3,4 er naboknuderne til node 1.
Når vi opdaterer en pris, skal vi følge nedenstående procedure:
Vi kan opdatere hver nodes omkostninger ved at bruge ovenstående formel. For eksempel var vi ved node 1, og vi var nødt til at opdatere prisen på dens tilstødende node 2,3,4.
Efter opdatering vil prisen eller vægten se sådan ud:
Trin 3) For node "2", naboer er 6 og 3. Vi opdaterer prisen til "6" ved at sammenligne uendelig (aktuel værdi). Omkostningerne ved node 2 + stiomkostninger fra 2 til 6. Man siger blot, at node “6” vil have prisen på 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, naboknudepunktet er 7. Så sammenligner vi den aktuelle værdi af knude 7 med stiomkostningen (7+1) eller 8, opdaterer vi prisen på knudepunkt 7. Det er 8.
Så vi finder en vej fra node 1 til node 7, og den er 1→ 3→ 7. Prisen er 8.
Trin 5) For node 4, vi vil opdatere dens tilstødende node omkostninger i overensstemmelse hermed. Så node "5" vil have en opdateret pris på 8. Efter trin 4,5 vil det se sådan ud:
Nu koster stien 1-3-7 8 (tidligere). Node "7" blev ikke markeret som besøgt, fordi vi kan nå node "7" fra node "6". Stien "1-2-6" havde en pris på 4. Så stien 1-2-6-7 vil koste 7.
Som 7 < 8, er det derfor, at den korteste vej fra kildepunktet "1" til destinationspunktet "7" vil være 1-2-6-7, og prisen er 7. Tidligere var den 1-3-7, og prisen 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.
Pseudokode Dijkstras algoritme
Her er pseudokoden til Dijkstras algoritme
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 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] & 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);
}
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] & 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)
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
Dijkstra Algo har et stort sæt anvendelser. Blandt dem er det meget brugt inden for netværk. Her er noget af den virkelige brug af Dijkstras algoritme:
Dijkstra på Google map: Grundlæggende er denne algoritme rygraden til at finde de korteste veje. Som vi kan se fra ovenstående kodestykke-output.
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 Map. Blandt disse stier er nogle stier sorteret fra for brugeren. Disse valgte stier er baseret på "tiden". Så "tid" er en fordel for den korteste vej.
Dijkstra i IP-routing: IP routing er en netværksterminologi. Det betyder, hvordan din datapakke sendes til modtageren via forskellige stier. Disse stier består af routere, servere osv. I IP-routing er der forskellige typer protokoller.
Disse protokoller hjælper routeren med at finde de korteste veje til at sende dataene. Et af protokolnavnene er "OSPF (Open Shortest Path First)". OSPF bruger dijkstra-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 Dijkstra-algoritmen.
Begrænsning af Dijkstras algoritme
Dijkstra-algoritmen kan ikke garantere den korteste vej i grafen med negativ kant. Dijkstra-algoritmen følger disse metoder:
- 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ølgende:
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 på den korteste vej.
Trin 3) Afstanden fra kildenoden 1 til noderne "2" og "3" er sat til uendelig, da den korteste vej endnu ikke er beregnet. Så enhver vej, der vil koste mindre end uendeligt, vil blive tilføjet til den korteste vej (grådig tilgang).
Trin 4) Opdatering af afstanden fra kildepunktet eller kildenoden "1" til "2". Den aktuelle vægt vil være 5 (5
Trin 5) Hvis vi nu tjekker de korteste afstande fra node "1", finder vi, at 5 er den korteste afstand for kant 1–> 2. Så node "2" vil blive markeret som besøgt.
På samme måde vil node "3" også blive markeret som besøgt, da den korteste afstand er 3.
Men hvis vi observerer, er der en sti 1-3-2, der kun vil koste 2. Men Dijkstra viser, at fra node "1" til node "2" er den korteste afstand 5. Så Dijkstra undlod at beregne den korteste afstand korrekt. Grunden til det skete er, at Dijkstra er en grådig algoritme. Så når først en knude er markeret som besøgt, vil den ikke blive genovervejet, selvom der kan være en kortere sti tilgængelig. Dette problem opstår kun, når kanterne har negative omkostninger eller negative vægtkanter
Dijkstra formår ikke at beregne den korteste vej mellem to knudepunkter i dette scenarie. Som et resultat har denne algoritme nogle ulemper. For at løse dette negative kantproblem bruges en anden algoritme kaldet "Bellman-Ford Algorithm". 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(V2). Her betyder udtrykket "0" en notation, der giver en antagelse for Dijkstra-algoritmen.
Vi kan gemme grafen ved hjælp af "Priority Queue". En prioritetskø er en binær heap-datastruktur. Det vil være mere effektivt end en 2D-matrix. En kant, der vil have en minimumsomkostning, vil have høj prioritet.
Så bliver tidskompleksiteten O (E log (V)). Her er E antallet af kanter, og V er antallet af hjørner.
Rumkompleksiteten er O(V2), da vi bruger en adjacency matrix (2D-array). Pladskompleksitet kan optimeres ved hjælp af en tilstødende liste eller kødatastruktur.
