Find den korteste vej mellem to punkter på en graf med Dijkstras algoritme

At finde den korteste sti mellem to punkter på en graf er et almindeligt problem i datastrukturer, især når det drejer sig om optimering.

En graf er en række noder forbundet med kanter. Grafer kan vægtes (kanter bærer værdier) og retningsbestemte (kanter har retning).

Nogle anvendelser af dette er optimering af flyveveje eller 6 grader af Kevin Bacon.

Dijkstras algoritme

Den mest almindelige løsning på dette problem er Dijkstras algoritme, der opdaterer den korteste sti mellem den aktuelle knude og alle dens naboer.

Efter opdatering af afstanden til alle naboerne bevæger den sig til noden med den laveste afstand og gentager processen med alle ubesøgte naboer. Denne proces fortsætter, indtil hele grafen er besøgt.

Billede af niveauer af kode

Trin 0:

Vores graf skal konfigureres, så vi kan registrere de krævede værdier. På enhver kant har vi afstanden mellem de to noder, den forbinder. På enhver knude har vi dens korteste afstand fra startknudepunktet.

Lad os indstille værdien på hver node til positiv uendelighed og indstille værdien på startknudepunktet til nul.

Trin 1:

Se på alle knudepunkter direkte ved siden af ​​startknudepunktet. De værdier, der bæres af kanterne, der forbinder starten, og disse tilstødende noder er de korteste afstande til hver respektive knude.

Registrer disse afstande på noden - overskrivende uendelig - og kryds også knudepunkterne, hvilket betyder, at deres korteste vej er fundet.

Trin 2:

Vælg en af ​​de noder, der har beregnet sin korteste sti, vi kalder dette vores omdrejningspunkt. Se på de knudepunkter, der støder op til det (vi kalder disse vores destinationsknudepunkter) og afstandene, der adskiller dem.

For hver destinationsnode:

  • Hvis værdien i omdrejningspunktet plus kantværdien, der forbinder den, udgør mindre end destinationsnodens værdi, skal du opdatere dens værdi, da der er fundet en ny kortere sti.
  • Hvis alle ruter til denne destinationsnode er blevet udforsket, kan den krydses af.

Trin 3:

Gentag trin 2, indtil alle noder er blevet krydset af. Vi har nu en graf, hvor værdierne i en hvilken som helst node vil være den korteste afstand til den fra startnoden.

Mere information:

Mere om Dijkstras algoritme

Andre korteste sti-algoritmer