Dijsktras algoritme: C++, Python Kodeeksempel
Sarah Chen
Hva er korteste vei eller korteste avstand?
En bane fra kildepunktet til destinasjonspunktet som koster et minimum, er den korteste veien eller korteste avstanden. I grafteori er det mulig å ha flere ruter fra en kilde til en destinasjon. Mellom disse rutene, hvis det er en rute som koster et minimumsbeløp, kan vi kalle det den korteste veialgoritmen.
Her betyr "Kostnad" antall noder i ruten eller summeringen av kostnader på hver vei. En bane kan ha én eller flere kanter. Forbindelsen mellom to hjørner kalles "kant". Det finnes ulike typer korteste vei-algoritmer, som Dijkstras algoritme, Bellman-Ford-algoritme, etc.
Her diskuterer vi om Dijkstras algoritme
La oss se på følgende vektede graf:
- Begrepet "vektet" betyr å flytte kostnader fra en node til en annen. Hvis du for eksempel flytter fra node 1 til node 2, er kostnaden eller vekten 1.
- Banen mellom node 1 til node 2 kalles kanten.
- "Udirigert" betyr at du kan flytte en node til en annen og tilbake til forrige node. Så hvis vi prøver å finne alle rutene fra node 1 til node 7, vil det være:
| Rute eller sti | Kostnad |
|---|---|
| 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 |
Blant disse fire rutene kan vi se at den første ruten vil koste oss 7. Så det er den korteste veien kostnadsmessig.
Hvordan Dijkstras algoritme fungerer
Dijkstra-algoritmen kan finne den korteste avstanden i både rettede og urettede 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. Så Dijkstras algoritme finner alle de korteste veiene fra en enkelt destinasjonsnode. Som et resultat oppfører den seg som en grådig algoritme.
I «eksempel»-delen nedenfor ser du trinn-for-trinn-tilnærmingen. Det fungerer som følger:
Trinn 1) Initialiser startnoden med 0 kostnader og resten av noden som Infinity Cost.
Trinn 2) Oppretthold en matrise eller liste for å holde styr på de besøkte nodene
Trinn 3) Oppdater nodekostnaden med minimumskostnaden. Det kan gjøres ved å sammenligne dagens kostnad med banekostnaden. (Demonstrasjon er vist 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 den korteste stifinningsalgoritmen, og BFS, DFS er stifinningsalgoritmen. I generelle tilfeller vurderer ikke BFS og DFS kostnadene mens de finner banen. Så disse algoritmene kan ikke garantere den korteste veien.
2D grid demonstrasjon av hvordan BFS fungerer
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.
Men la oss se en eksempelgraf:
Her finner den en sti i nivå 2. BFS krysser grafen i nivårekkefølge. Så den reiser slik:
Trinn 1) Start fra node "1" og besøk alle tilstøtende noder 2,3,4
Trinn 2) Merk node 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 destinasjonsnoden.
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 dybder eller 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.
Når det gjelder Dijkstra-algoritmen, vil den imidlertid velge kanter basert på kostnadene deres. Som en grådig algoritme vil den velge den beste eller laveste kostnadsveien.
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 veiene ved å beregne vekter. Den vil ikke søke etter alle mulige veier. La oss demonstrere Dijkstras algoritme med et eksempel. Du har for eksempel blitt bedt om å finne den korteste veien fra node 1 til 7.
For denne prosessen er trinnene gitt nedenfor:
Trinn 1) Initialiser startnodekostnaden til 0.
Resten av noden, tilordne "Inf". Det betyr at det ikke finnes noen sti mellom startpunktet (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 hver nodes kostnad ved å bruke formelen ovenfor. For eksempel var vi på node 1, og vi trengte å oppdatere kostnadene for den tilstøtende noden 2,3,4.
Etter oppdatering vil kostnaden eller vekten se slik ut:
Trinn 3) For node "2", naboer er 6 og 3. Vi oppdaterer kostnaden til "6" ved å sammenligne uendelig (nåværende verdi). Kostnaden for node 2 + banekostnad fra 2 til 6. Bare si at node "6" vil ha en kostnad på 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, nabonoden er 7. Så hvis vi sammenligner den nåværende verdien av node 7 med banekostnaden (7+1) eller 8, vil vi oppdatere kostnadene for node 7. Det vil si 8.
Så vi finner en vei fra node 1 til node 7, og den er 1→ 3→ 7. Kostnaden er 8.
Trinn 5) For node 4, vi vil oppdatere dens tilstøtende nodekostnad tilsvarende. Så node "5" vil ha en oppdatert kostnad på 8. Etter trinn 4,5 vil det se slik ut:
Nå har banen 1-3-7 prisen på 8 (tidligere). Node "7" ble ikke merket som besøkt fordi vi kan nå node "7" fra node "6". Banen "1-2-6" hadde en kostnad på 4. Så banen 1-2-6-7 vil koste 7.
Som 7 < 8, er det derfor den korteste veien fra kildetoppunktet "1" til destinasjonspunktet "7" vil 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.
Pseudokode Dijkstras algoritme
Her er pseudokoden for 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 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] & 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);
}
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] & 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)
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
Dijkstra Algo har et stort sett med bruksområder. Blant disse er det mye brukt innen nettverksbygging. Her er noe av den virkelige bruken av Dijkstras algoritme:
Dijkstra på Google map: I utgangspunktet er denne algoritmen ryggraden for å finne de korteste veiene. Som vi kan se fra kodebiten 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 Map. Blant disse banene er noen stier sortert ut for brukeren. Disse valgte banene er basert på "tiden". Så "tid" er en fordel for den korteste veien.
Dijkstra i IP-ruting: IP-ruting er en nettverksterminologi. Det betyr hvordan datapakken din sendes til mottakeren via forskjellige veier. Disse banene består av rutere, servere osv. I IP-ruting finnes det ulike typer protokoller.
Disse protokollene hjelper ruteren med å finne de korteste veiene for å sende dataene. Et av protokollnavnene er "OSPF (Open Shortest Path First)". OSPF bruker dijkstra-algoritmen. Ruteren opprettholder en rutetabell. Hver ruter deler bordet sitt med naborutere. Etter å ha mottatt den oppdaterte tabellen, må de beregne alle banene på nytt. På den tiden bruker ruteren Dijkstra-algoritmen.
Begrensning av Dijkstras algoritme
Dijkstra-algoritmen kan ikke garantere den korteste veien i grafen med negativ kant. Dijkstra-algoritmen følger disse metodene:
- 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 som følgende:
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 veien.
Trinn 3) Avstanden fra kildenoden 1 til nodene "2" og "3" er satt til uendelig, da den korteste veien ennå ikke er beregnet. Så enhver vei som vil koste mindre enn uendelig vil bli lagt til den korteste veien (grådig tilnærming).
Trinn 4) Oppdatering av avstanden fra kildetoppunktet eller kildenoden "1" til "2". Den nåværende vekten vil være 5 (5
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å merkes som besøkt ettersom den korteste avstanden er 3.
Imidlertid, hvis vi observerer, er det en bane 1-3-2 som vil koste bare 2. Men Dijkstra viser at fra node "1" til node "2," er den korteste avstanden 5. Så Dijkstra klarte ikke å beregne den korteste riktig avstand. Grunnen til at det skjedde er at Dijkstra er en grådig algoritme. Så når en node er merket som besøkt, vil den ikke bli revurdert, selv om det kan være en kortere vei 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 Algorithm". Den 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(V2). Her betyr begrepet "0" en notasjon som gir en antakelse for Dijkstra-algoritmen.
Vi kan lagre grafen ved å bruke "Prioritetskøen". En prioritetskø er en binær haugdatastruktur. Det vil være mer effektivt enn en 2D-matrise. En kant som vil ha en minimumskostnad vil ha høy prioritet.
Da blir tidskompleksiteten O(E log(V)). Her er E antall kanter, og V er antall topper.
Romkompleksiteten er O(V2), da vi bruker en tilstøtende matrise (2D-array). Plasskompleksitet kan optimaliseres ved hjelp av en tilstøtende liste eller kødatastruktur.
