Dijkstras algoritme

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 23. februar 2022; checks kræver 8 redigeringer .

Dijkstras algoritme er en grafalgoritme opfundet af den hollandske videnskabsmand Edsger Dijkstra i 1959 . Finder de korteste veje fra et af grafens hjørner til alle de andre. Algoritmen virker kun for grafer uden kanter med negativ vægt . Algoritmen er meget udbredt i programmering, for eksempel bruges den af OSPF- og IS-IS- routingprotokollerne .

Problemformulering

Eksempler

Mulighed 1. Givet et netværk af veje, der forbinder byerne i Moskva-regionen. Nogle veje er ensrettede. Find de korteste veje fra by A til hver by i regionen (hvis du kun kan bevæge dig ad veje).

Mulighed 2. Der er et antal flyvninger mellem verdens byer, prisen er kendt for hver. Prisen på en flyvning fra A til B er muligvis ikke lig med prisen på en flyvning fra B til A. Find minimumsomkostningsruten (eventuelt med overførsler) fra København til Barnaul .

Formel definition

Givet en vægtet rettet [1] graf uden buer med negativ vægt [2] . Find de korteste veje fra et eller andet toppunkt på grafen til alle andre toppunkter på denne graf. $G(V,E)$ $-en$ $G$

Uformel forklaring

Hvert toppunkt fra V er tildelt en etiket — den mindste kendte afstand fra dette toppunkt til en .

Algoritmen arbejder trin for trin - ved hvert trin "besøger" den ét toppunkt og forsøger at reducere etiketter.

Algoritmen afsluttes, når alle hjørner er besøgt.

Initialisering .

Etiketten for selve toppunktet a antages at være 0, etiketterne for de andre toppunkter er sat til uendelig.

Dette afspejler, at afstandene fra a til andre toppunkter endnu ikke er kendt.

Alle hjørner af grafen er markeret som ubesøgte.

Algoritme trin .

Hvis alle hjørner er besøgt, afsluttes algoritmen.

Ellers vælges toppunktet u med minimumsmærket fra de endnu ikke besøgte toppunkter .

Vi overvejer alle mulige ruter, hvor u er det næstsidste punkt. De toppunkter, som kanterne fra u fører til, kaldes naboerne til dette toppunkt. For hver nabo til u , undtagen dem, der er markeret som besøgt, skal du overveje en ny vejlængde svarende til summen af værdierne af den aktuelle etiket u og længden af kanten, der forbinder u med denne nabo.

Hvis den modtagne længdeværdi er mindre end etiketværdien for naboen, skal etiketværdien erstattes med den opnåede længdeværdi. Efter at have overvejet alle naboerne, markerer vi toppunktet u som besøgt og gentager trinnet i algoritmen .

Eksempel

Overvej udførelsen af algoritmen på eksemplet på grafen vist i figuren.

Lad det være påkrævet at finde de korteste afstande fra 1. toppunkt til alle de andre.

Cirklerne angiver hjørnerne, linjerne angiver stierne mellem dem (kanterne på grafen).

Antallet af hjørner er angivet i cirklerne, deres vægt er angivet over kanterne - længden af stien.

Ved siden af hvert toppunkt er der markeret en rød etiket - længden af den korteste vej til dette toppunkt fra toppunkt 1.

Første skridt .

Vertex 1 har minimumsmærket. Vertices 2, 3 og 6 er dens naboer.

Den første nabo til toppunkt 1 er igen toppunkt 2, fordi længden af stien dertil er minimal.

Længden af stien til den gennem toppunkt 1 er lig med summen af værdien af etiketten for toppunkt 1 og længden af kanten, der går fra 1. til 2., det vil sige 0 + 7 = 7.

Dette er mindre end den nuværende etiket for toppunkt 2, uendelig, så den nye etiket for 2. toppunkt er 7.

Vi udfører en lignende operation med to andre naboer til 1. vertex - 3. og 6.

Alle naboer til node 1 er kontrolleret.

Den nuværende minimumsafstand til topmøde 1 betragtes som endelig og er ikke genstand for revision.

Kryds det ud af grafen for at markere, at dette toppunkt er blevet besøgt.

Andet trin .

Igen finder vi det "nærmeste" af de ubesøgte hjørner. Dette er toppunkt 2 mærket 7.

Igen forsøger vi at reducere etiketterne for naboerne til det valgte toppunkt og forsøger at passere gennem dem gennem det 2. toppunkt. Vertex 2's naboer er toppunkter 1, 3 og 4.

Den første (i rækkefølge) nabo til toppunkt 2 er toppunkt 1. Men det er allerede besøgt, så vi gør ikke noget med 1. toppunkt.

Den næste nabo er toppunkt 3, da den har minimumsmærket.

Hvis du går til det gennem 2, så vil længden af en sådan sti være lig med 17 (7 + 10 = 17). Men den aktuelle etiket for det tredje toppunkt er 9, hvilket er mindre end 17, så etiketten ændres ikke.

En anden nabo til toppunkt 2 er toppunkt 4.

Hvis du går til det gennem 2., så vil længden af en sådan sti være lig med summen af den korteste afstand til 2. toppunkt og afstanden mellem toppunkter 2 og 4, det vil sige 22 (7 + 15 = 22) .

Siden 22< sætter vi etiketten for toppunkt 4 til 22. $\infty$

Alle naboer til top 2 er blevet set, vi fryser afstanden til den og markerer den som besøgt.

Tredje trin .

Vi gentager trinnet i algoritmen ved at vælge toppunkt 3. Efter dens "behandling" får vi følgende resultater:

Næste trin .

Vi gentager trinnet i algoritmen for de resterende hjørner. Disse vil være henholdsvis hjørnerne 6, 4 og 5.

Afslutning af algoritmeudførelsen .

Algoritmen afsluttes, når alle hjørner er besøgt.

Resultatet af algoritmen er synligt i den sidste figur: den korteste vej fra toppunkt 1 til 2 er 7, til 3 er 9, til 4 er 20, til 5 er 20, til 6 er 11.

Hvis alle ubesøgte hjørner på et tidspunkt er markeret med uendelighed, betyder det, at disse hjørner ikke kan nås (det vil sige, at grafen ikke er forbundet ). Så kan algoritmen færdiggøres før tidsplanen.

Algoritme

Notation

$V$ er sættet af grafens toppunkter
$E$ er sættet af grafkanter
$w[ij]$ - vægt (længde) af ribben $ij$
$-en$ - toppunktet, hvorfra afstandene søges
$U$ - sæt af besøgte hjørner
$d[u]$ — i slutningen af algoritmen er lig med længden af den korteste vej fra til toppen $-en$ $u$
$p[u]$ — i slutningen af algoritmen indeholder den korteste vej fra til $-en$ $u$
$v$ er det aktuelle toppunkt, der betragtes af algoritmen

Algoritmeimplementeringskode

Nedenfor er koden til implementering af algoritmen i programmeringssproget Java . Denne implementeringsmulighed er ikke den bedste, men viser tydeligt den mulige implementering af algoritmen:

klasse Dijkstra { dobbelt [] dist = ny dobbelt [ GV () ] ; Kant [] pred = ny Kant [ GV () ] ; public Dijkstra ( WeightedDigraph G , int s ) { boolean [] markeret = ny boolean [ GV () ] ; for ( int v = 0 ; v < GV ( ); v ++ ) dist [ v ] = Dobbelt . POSITIVE_INFINITY ; MinPQplus < Double , Integer > pq ; pq = new MinPQplus < Double , Integer > (); \\ Prioritetskø _ dist [ s ] = 0,0 ; pq . sætte ( dist [ s ] , s ); while ( ! pq . isEmpty ()) { intv = pq . _ delmin (); if ( markeret [ v ] ) fortsæt ; markeret ( v ) = sand ; for ( Edge e ( v )) { int w = e . til (); if ( dist [ w ]> dist [ v ] + e . vægt ()) { dist [ w ] = dist [ v ] + e . vægt (); pred [ w ] = e ; pq . indsætte ( dist [ w ] , w ); } } } } }

Pseudokode

Tildel

$d[a]\får 0,\ p[a]\får 0$

For alle andre end , tildeler vi . $u\i V$ $-en$ $d[u]\bliver\infty$

Farvel . Lad være et toppunkt med minimum $\eksisterer v\notin U$ $v\notin U$ $d[v]$ $v$ $U$

Til alle dem, der $u\notin U$ $vu\in E$

hvis da $d[u]>d[v]+w[vu]$

lave om $d[u]\får d[v]+w[vu]$

lave om $p[u]\gets (p[v],u)$

Beskrivelse

I den enkleste implementering kan en matrix af tal bruges til at gemme tallene d [ i ], og en matrix af booleske variabler kan bruges til at lagre medlemskabet af et element i sættet U.

I begyndelsen af algoritmen antages afstanden for det indledende toppunkt at være nul, og alle andre afstande er fyldt med et stort positivt tal (større end den maksimalt mulige vej i grafen ). Flag-arrayet er fyldt med nuller. Så starter hovedsløjfen.

Ved hvert trin i sløjfen leder vi efter et toppunkt med en minimumsafstand og et flag lig nul. Derefter sætter vi flaget til 1 i det og kontrollerer alle de hjørner, der støder op til det . Hvis afstanden i dem (i ) er større end summen af afstanden til det aktuelle toppunkt og længden af kanten, så reducerer vi den. Sløjfen slutter, når flagene for alle hjørner bliver lig med 1, eller når alle hjørner med flaget er 0 . Sidstnævnte tilfælde er muligt, hvis og kun hvis grafen G er afbrudt. $v$ $u$ $u$ $d[i]=\infty$

Bevis for rigtighed

Lade være længden af den korteste vej fra toppunkt til toppunkt . Lad os bevise ved induktion , at ligheden gælder i det øjeblik, vi besøger et hvilket som helst vertex . $l(v)$ $-en$ $v$ $z$ $d(z)=l(z)$

Grundlag. Toppunktet besøges først . I dette øjeblik . $-en$ $d(a)=l(a)=0$

Trin. Lad os sige, at vi har valgt en top at besøge . Lad os bevise det i dette øjeblik . Til at begynde med bemærker vi, at for ethvert toppunkt holder det altid (algoritmen kan ikke finde en sti, der er kortere end den korteste af alle eksisterende). Lad være den korteste vej fra til . Toppen er på og ikke besøgt. Derfor er sættet af ubesøgte hjørner ikke tomt. Lad være den første ubesøgte toppunkt på , og være den, der går forud (derfor besøgt). Da stien er den korteste, er den del, der fører fra gennem til , også den korteste, derfor . $z\neq a$ $d(z)=l(z)$ $v$ $d(v)\geq l(v)$ $P$ $-en$ $z$ $z$ $P$ $P$ $y$ $P$ $x$ $P$ $-en$ $x$ $y$ $l(y)=l(x)+w(xy)$

Ved induktionshypotesen, i det øjeblik, man besøgte vertexet , , Derfor modtog vertexet en etiket, der ikke var større end . Derfor ,. Hvis , så er induktionstrinnet bevist. Ellers, da vertex i øjeblikket er valgt og ikke , er etiketten minimal blandt de ubesøgte, dvs. Ved at kombinere dette med , har vi , hvilket skulle bevises. $x$ $d(x)=l(x)$ $y$ $d(x)+w(xy)=l(x)+w(xy)=l(y)$ $d(y)=l(y)$ $z=y$ $z$ $y$ $z$ $d(z)\leq d(y)=l(y)\leq l(z)$ $d(z)\geq l(z)$ $d(z)=l(z)$

Fordi algoritmen afsluttes, når alle toppunkter er besøgt, på det tidspunkt for alle toppunkter. $d=l$

Algoritmens kompleksitet

Kompleksiteten af Dijkstras algoritme afhænger af, hvordan vertexet v findes , hvordan sættet af ubesøgte hjørner er lagret, og hvordan etiketterne opdateres. Angiv med n antallet af hjørner, og med m antallet af kanter i grafen G .

I det enkleste tilfælde, når hele sættet af toppunkter søges for at finde toppunktet med minimum d [ v ], og et array bruges til at gemme værdierne af d , er algoritmens køretid . Hovedsløjfen udføres ca. n gange, i hver af dem bruges ca. n operationer på at finde minimum. At cykle gennem naboerne til hvert besøgt vertex tager et antal operationer proportionalt med antallet af kanter m (da hver kant forekommer nøjagtigt to gange i disse cyklusser og kræver et konstant antal operationer). Således er den samlede køretid for algoritmen , men da , er det . $O(n^{2})$ $O(n^{2}+m)$ $m\leq n(n-1)$ $O(n^{2})$

For sparsomme grafer (det vil sige dem, for hvilke m er meget mindre end n²), kan ubesøgte hjørner gemmes i en binær bunke , og værdierne af d [ i ] kan bruges som en nøgle, så tid til at fjerne et toppunkt fra vil blive, mens ændringstiden øges til . Da løkken udføres omkring n gange, og antallet af etiketændringer ikke er mere end m , er køretiden for en sådan implementering . $\overline U$ $\log n$ $d[i]$ $\log n$ $O(n\log n+m\log n)$

Hvis vi bruger en Fibonacci-dynge til at gemme ubesøgte hjørner , for hvilke sletningen sker i gennemsnit for , og værdien falder i gennemsnit for , så vil køretiden for algoritmen være . Men ifølge Alekseevs og Talanovs forelæsninger [3] : $O(\log n)$ $O(1)$ $O(n\log n+m)$

de skjulte konstanter i de asymptotiske omkostningsestimater er store, og brugen af Fibonacci-dynger er sjældent passende: almindelige binære ( d-ary ) dynger er mere effektive i praksis.

Alternativer til dem er tykke dynger, tynde dynger og Brodal-dynger , som har de samme asymptotiske estimater, men mindre konstanter [4] .

Se også

Litteratur

Dijkstra E. W. En note om to problemer i forbindelse med grafer // Tal . Math / F. Brezzi - Springer Science + Business Media , 1959. - Vol. 1, Iss. 1. - S. 269-271. — ISSN 0029-599X ; 0945-3245 - doi:10.1007/BF01386390
Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmer: konstruktion og analyse = Introduktion til algoritmer. - 2. udg. - M .: "Williams" , 2006. - S. 1296. - ISBN 0-07-013151-1 .
Levitin A. V. Kapitel 9. Grådige metoder: Dijkstras algoritme // Algoritmer. Introduktion til udvikling og analyse - M . : Williams , 2006. - S. 189-195. — 576 s. — ISBN 978-5-8459-0987-9

Noter

↑ Særlige tilfælde af en rettet graf er urettede og blandede ("delvist rettede") grafer.
↑ For en graf med negative vægte bruges en mere generel algoritme - Dijkstra's Algorithm with Potentials
↑ Vladimir Alekseev, Vladimir Talanov, Kursus "Data Structures and Computation Models", Forelæsning nr. 7: Binomial and Fibonacci Heaps // 09/26/2006, Intuit.ru
↑ Vladimir Alekseev, Vladimir Talanov, Kursus "Data Structures and Computation Models", Foredrag nr. 8: Thin Heaps // 09/26/2006, Intuit.ru

Algoritmer til grafsøgning
Uoplyste metoder	Tovejssøgning Strålesøgning Leksikografisk bredde første søgning Bredde først søgning Søg efter omkostningskriterium Dybde første søgning Backtracking søgning Søg ved at klatre til toppen Dybdebegrænset søgning Dybde-første søgning med iterativ uddybning
Informerede metoder	Alfa beta klipning Gren og bundet metode Søg efter første bedste match EN* B* D* At finde et overgangspunkt IDA* Rekursiv søgning på det første bedste match SMA*
Genveje	Bølgealgoritme Bellman-Ford algoritme Dijkstras algoritme Johnsons algoritme Levits algoritme Floyd-Warshall algoritme Kantsøgning
Minimumspændende træ	Boruvkas algoritme Prims algoritme Kruskals algoritme
Andet	British Museum Algoritme Edmonds algoritme Trækøring Nærmeste nabo-algoritme i problemet med rejsende sælger