Dijkstras korteste sti-algoritme - en detaljeret og visuel introduktion

Velkommen! Hvis du altid har ønsket at lære og forstå Dijkstras algoritme, så er denne artikel noget for dig. Du vil se, hvordan det fungerer bag kulisserne med en trinvis grafisk forklaring.

Du vil lære:

  • Grundlæggende grafkoncepter (en hurtig gennemgang).
  • Hvad Dijkstras algoritme bruges til.
  • Hvordan det fungerer bag kulisserne med et trin-for-trin eksempel.

Lad os begynde. ✨

? Introduktion til grafer

Lad os starte med en kort introduktion til grafer.

Basale koncepter

Grafer er datastrukturer, der bruges til at repræsentere "forbindelser" mellem par af elementer.

  • Disse elementer kaldes noder . De repræsenterer virkelige objekter, personer eller enheder.
  • Forbindelserne mellem noder kaldes kanter .

Dette er en grafisk gengivelse af en graf:

Noder er repræsenteret med farvede cirkler, og kanter er repræsenteret med linjer, der forbinder disse cirkler.

Tip: To noder er forbundet, hvis der er en kant mellem dem.

Ansøgninger

Grafer er direkte anvendelige til virkelige scenarier. For eksempel kunne vi bruge grafer til at modellere et transportnetværk, hvor noder repræsenterer faciliteter, der sender eller modtager produkter, og kanter repræsenterer veje eller stier, der forbinder dem (se nedenfor).

Typer af grafer

Grafer kan være:

  • Ikke omdirigeret: hvis du for hvert par tilsluttede noder kan gå fra den ene node til den anden i begge retninger.
  • Regisseret: hvis du for hvert par tilsluttede noder kan du kun gå fra en node til en anden i en bestemt retning. Vi bruger pile i stedet for enkle linjer til at repræsentere rettet kanter.

? Tip: I denne artikel vil vi arbejde med ikke-rettede grafer.

Vægtede grafer

En vægtgraf er en graf, hvis kanter har en "vægt" eller "pris". Vægten af ​​en kant kan repræsentere afstand, tid eller noget, der modellerer "forbindelsen" mellem det par noder, den forbinder.

For eksempel kan du i det vægtede diagram nedenfor se et blåt tal ved siden af ​​hver kant. Dette tal bruges til at repræsentere vægten af ​​den tilsvarende kant.

? Tip: Disse vægte er vigtige for Dijkstras algoritme. Du vil se hvorfor om bare et øjeblik.

? Introduktion til Dijkstras algoritme

Nu hvor du kender de grundlæggende begreber i grafer, lad os begynde at dykke ned i denne fantastiske algoritme.

  • Formål og brugssager
  • Historie
  • Grundlæggende om algoritmen
  • Krav

Formål og brugssager

Med Dijkstras algoritme kan du finde den korteste sti mellem noder i en graf. Især kan du finde den korteste sti fra en node (kaldet "kilde-node") til alle andre noder i grafen og producere et kort med kort sti.

Denne algoritme bruges i GPS-enheder til at finde den korteste sti mellem den aktuelle placering og destinationen. Det har brede applikationer i industrien, især inden for domæner, der kræver modelleringsnetværk.

Historie

Denne algoritme blev oprettet og udgivet af Dr. Edsger W. Dijkstra, en genial hollandsk computerforsker og softwareingeniør.

I 1959 offentliggjorde han en 3-siders artikel med titlen "En note om to problemer i forbindelse med grafer", hvor han forklarede sin nye algoritme.

Under et interview i 2001 afslørede Dr. Dijkstra, hvordan og hvorfor han designet algoritmen:

Hvad er den korteste måde at rejse fra Rotterdam til Groningen på? Det er algoritmen for den korteste vej, som jeg designede på cirka 20 minutter. En morgen handlede jeg i Amsterdam med min unge forlovede og trætte, vi satte os på caféterrassen for at drikke en kop kaffe, og jeg tænkte bare på, om jeg kunne gøre dette, og jeg designede derefter algoritmen til den korteste vej . Som jeg sagde, var det en 20-minutters opfindelse. Faktisk blev den udgivet i 1959, tre år senere. Publikationen er stadig ganske flot. En af grundene til at det er så rart var, at jeg designede det uden blyant og papir. Uden blyant og papir er du næsten tvunget til at undgå al kompleksitet, der kan undgås. Til sidst blev denne algoritme til min store forbløffelse en af ​​hjørnestenene i min berømmelse. - Som citeret i artiklen Edsger W.Dijkstra fra Et interview med Edsger W. Dijkstra.

Utroligt, ikke? På bare 20 minutter designede Dr. Dijkstra en af ​​de mest berømte algoritmer i datalogiets historie.

Grundlæggende om Dijkstras algoritme

  • Dijkstras algoritme starter grundlæggende ved den node, du vælger (kildeknudepunktet), og den analyserer grafen for at finde den korteste sti mellem den knude og alle de andre knudepunkter i grafen.
  • Algoritmen holder styr på den aktuelt kendte korteste afstand fra hver knude til kildeknudepunktet, og den opdaterer disse værdier, hvis den finder en kortere sti.
  • Når algoritmen har fundet den korteste sti mellem kildeknudepunktet og en anden knudepunkt, markeres den knudepunkt som "besøgt" og føjes til stien.
  • Processen fortsætter, indtil alle noder i grafen er blevet føjet til stien. På denne måde har vi en sti, der forbinder kildeknudepunktet med alle andre knudepunkter, der følger den kortest mulige sti for at nå hver knudepunkt.

Krav

Dijkstras algoritme kan kun arbejde med grafer, der har positive vægte. Dette skyldes, at vægten af ​​kanterne under processen skal tilføjes for at finde den korteste vej.

Hvis der er en negativ vægt i grafen, fungerer algoritmen ikke korrekt. Når en node er blevet markeret som "besøgt", markeres den aktuelle sti til den node som den korteste sti til at nå den node. Og negative vægte kan ændre dette, hvis den samlede vægt kan reduceres, efter at dette trin er sket.

? Eksempel på Dijkstras algoritme

Nu hvor du ved mere om denne algoritme, lad os se, hvordan den fungerer bag kulisserne med et trin for trin-eksempel.

Vi har denne graf:

Algoritmen genererer den korteste sti fra node 0til alle de andre noder i grafen.

? Tip: For denne graf antager vi, at vægten af ​​kanterne repræsenterer afstanden mellem to noder.

Vi har den korteste sti fra node 0til node 1, fra node 0til node 2, fra node 0til node 3og så videre for hver node i grafen.

Oprindeligt har vi denne liste over afstande (se listen nedenfor):

  • Afstanden fra kildeknudepunktet til sig selv er 0. I dette eksempel vil kildeknudepunktet være node, 0men det kan være en hvilken som helst node, du vælger.
  • Afstanden fra kildeknudepunktet til alle andre knudepunkter er endnu ikke bestemt, så vi bruger uendeligt symbolet til at repræsentere dette oprindeligt.

Vi har også denne liste (se nedenfor) for at holde styr på de noder, der endnu ikke er besøgt (noder, der ikke er inkluderet i stien):

Tip: Husk, at algoritmen er afsluttet, når alle noder er blevet føjet til stien.

Da vi vælger at starte ved node 0, kan vi markere denne node som besøgt. Tilsvarende krydser vi den fra listen over ubesøgte noder og tilføjer en rød kant til den tilsvarende node i diagrammet:

Nu skal vi begynde at kontrollere afstanden fra node 0til dens tilstødende noder. Som du kan se, er dette noder 1og 2(se de røde kanter):

Tip: Dette betyder ikke, at vi straks tilføjer de to tilstødende noder til den korteste sti. Før vi tilføjer en knude til denne sti, skal vi kontrollere, om vi har fundet den korteste vej til at nå den. Vi laver simpelthen en indledende undersøgelsesproces for at se de tilgængelige muligheder.

Vi har brug for at opdatere afstandene fra node 0til node 1og node 2med vægten af ​​de kanter, der forbinder dem til node 0(kildeknudepunktet). Disse vægte er henholdsvis 2 og 6:

Efter opdatering af afstanden til de tilstødende noder skal vi:

  • Vælg den knude, der er tættest på kildeknudepunktet baseret på de aktuelle kendte afstande.
  • Marker det som besøgt.
  • Føj det til stien.

Hvis vi tjekker listen over afstande, kan vi se, at noden 1har den korteste afstand til kildeknudepunktet (en afstand på 2), så vi tilføjer den til stien.

I diagrammet kan vi repræsentere dette med en rød kant:

Vi markerer det med en rød firkant på listen for at repræsentere, at den er "besøgt", og at vi har fundet den korteste vej til denne knude:

Vi krydser den fra listen over ubesøgte noder:

Nu skal vi analysere de nye tilstødende noder for at finde den korteste vej til at nå dem. Vi analyserer kun de noder, der støder op til de noder, der allerede er en del af den korteste sti (stien markeret med røde kanter).

Node 3og node 2er begge ved siden af ​​noder, der allerede er i stien, fordi de er direkte forbundet med henholdsvis node 0og node 1, som du kan se nedenfor. Dette er de noder, som vi vil analysere i næste trin.

Da vi allerede har registreret afstanden fra kildeknudepunktet til knudepunktet 2på vores liste, behøver vi ikke opdatere afstanden denne gang. Vi behøver kun at opdatere afstanden fra kildeknudepunktet til den nye tilstødende knudepunkt (knudepunkt 3):

Denne afstand er 7 . Lad os se hvorfor.

For at finde afstanden fra kildeknudepunktet til en anden knudepunkt (i dette tilfælde knudepunkt 3) tilføjer vi vægten af ​​alle de kanter, der danner den korteste sti for at nå den knude:

  • For node 3: den samlede afstand er 7, fordi vi tilføjer vægten af ​​de kanter, der danner stien 0 -> 1 -> 3(2 for kanten 0 -> 1og 5 for kanten 1 -> 3).

Nu hvor vi har afstanden til de tilstødende knudepunkter, skal vi vælge, hvilken node der skal føjes til stien. Vi skal vælge den ikke- besøgte node med den korteste (i øjeblikket kendte) afstand til kildeknudepunktet.

Fra listen over afstande kan vi straks registrere, at dette er node 2med afstand 6 :

Vi tilføjer det grafisk til stien med en rød kant omkring knudepunktet og en rød kant:

Vi markerer det også som besøgt ved at tilføje en lille rød firkant på listen over afstande og krydse den fra listen over ubesøgte noder:

Nu skal vi gentage processen for at finde den korteste sti fra kildeknudepunktet til den nye tilstødende knudepunkt, som er node 3.

Du kan se, at vi har to mulige stier 0 -> 1 -> 3eller 0 -> 2 -> 3. Lad os se, hvordan vi kan beslutte, hvilken der er den korteste vej.

Node har 3allerede en afstand på listen, der blev optaget tidligere ( 7, se listen nedenfor). Denne afstand var resultatet af et tidligere trin, hvor vi tilføjede vægte 5 og 2 af de to kanter, som vi havde brug for at krydse for at følge stien 0 -> 1 -> 3.

Men nu har vi et andet alternativ. Hvis vi vælger at følge stien 0 -> 2 -> 3, skal vi følge to kanter 0 -> 2og 2 -> 3med vægt 6 og 8 ,henholdsvis,som repræsenterer en samlet afstand på 14 .

Det er klart, at den første (eksisterende) afstand er kortere (7 mod 14), så vi vælger at beholde den oprindelige sti 0 -> 1 -> 3. Vi opdaterer kun afstanden, hvis den nye sti er kortere.

Derfor tilføjer vi denne node til stien ved hjælp af den første alternativ: 0 -> 1 -> 3.

Vi markerer denne node som besøgt og krydser den fra listen over ubesøgte noder:

Nu gentager vi processen igen.

Vi er nødt til at kontrollere de nye tilstødende noder, som vi hidtil ikke har besøgt. Denne gang er disse noder node 4og node, 5da de støder op til node 3.

Vi opdaterer afstande af disse noder til kildeknudepunktet og forsøger altid at finde en kortere sti, hvis det er muligt:

  • For node 4: afstanden er 17 fra stien   0 -> 1 -> 3 -> 4.
  • For node 5: afstanden er 22 fra stien 0 -> 1 -> 3 -> 5.

? Tip: Bemærk, at vi kun kan overveje at udvide den korteste sti (markeret med rødt). Vi kan ikke overveje stier, der fører os gennem kanter, der ikke er føjet til den korteste sti (for eksempel kan vi ikke danne en sti, der går gennem kanten 2 -> 3).

Vi er nødt til at vælge hvilken ubesøgt node, der skal markeres som besøgt nu. I dette tilfælde er det knudepunkt, 4fordi det har den korteste afstand på listen over afstande. Vi tilføjer det grafisk i diagrammet:

Vi markerer det også som "besøgt" ved at tilføje en lille rød firkant på listen:

Og vi krydser den fra listen over ubesøgte noder:

Og vi gentager processen igen. Vi kontrollerer de tilstødende noder: node 5og node 6. Vi er nødt til at analysere hver mulig sti, som vi kan følge for at nå dem fra noder, der allerede er markeret som besøgt og føjet til stien.

Til knude 5:

  • Den første mulighed er at følge stien 0 -> 1 -> 3 -> 5, som har en afstand på 22 fra kildeknudepunktet (2 + 5 + 15). Denne afstand var allerede registreret på listen over afstande i et tidligere trin.
  • Den anden mulighed ville være at følge stien 0 -> 1 -> 3 -> 4 -> 5, som har en afstand på 23 fra kildeknudepunktet (2 + 5 + 10 + 6).

Det er klart, at den første sti er kortere, så vi vælger den til node 5.

Til knude 6:

  • Den tilgængelige sti er 0 -> 1 -> 3 -> 4 -> 6, som har en afstand på 19 fra kildeknudepunktet (2 + 5 + 10 + 2).

Vi markerer noden med den korteste (i øjeblikket kendte) afstand som besøgt. I dette tilfælde knude 6.

Og vi krydser den fra listen over ubesøgte noder:

Nu har vi denne sti (markeret med rødt):

Kun en node er endnu ikke besøgt, node 5. Lad os se, hvordan vi kan inkludere det i stien.

Der er tre forskellige stier, som vi kan tage for at nå noden 5fra de noder, der er blevet føjet til stien:

  • Mulighed 1:0 -> 1 -> 3 -> 5 med en afstand på 22 (2 + 5 + 15).
  • Mulighed 2:0 -> 1 -> 3 -> 4 -> 5 med en afstand på 23 (2 + 5 + 10 + 6).
  • Mulighed 3:0 -> 1 -> 3 -> 4 -> 6 -> 5 med en afstand på 25 (2 + 5 + 10 + 2 + 6).

Vi vælger den korteste sti: 0 -> 1 -> 3 -> 5med en afstand på 22 .

Vi markerer noden som besøgt og krydser den fra listen over ubesøgte noder:

Og voilà! Vi har det endelige resultat med den korteste sti fra node 0til hver node i grafen.

I diagrammet markerer de røde linjer de kanter, der hører til den korteste sti. Du skal følge disse kanter for at følge den korteste sti for at nå en given node i grafen startende fra node 0.

For eksempel, hvis du vil nå node 6startende fra node 0, skal du bare følge de røde kanter, og du følger 0 -> 1 -> 3 -> 4 - > 6automatisk den korteste sti .

? Sammenfattende

  • Grafer bruges til at modellere forbindelser mellem objekter, mennesker eller enheder. De har to hovedelementer: knuder og kanter. Noder repræsenterer objekter, og kanter repræsenterer forbindelserne mellem disse objekter.
  • Dijkstras algoritme finder den korteste sti mellem en given knude (som kaldes "kildeknudepunktet") og alle andre knudepunkter i en graf.
  • Denne algoritme bruger vægten af ​​kanterne til at finde den sti, der minimerer den samlede afstand (vægt) mellem kildeknudepunktet og alle andre noder.

Jeg håber virkelig, du kunne lide min artikel og fandt det nyttigt. Nu ved du, hvordan Dijkstras algoritme fungerer bag kulisserne. Følg mig på Twitter @ EstefaniaCassN og tjek mine online kurser.