Dijkstras algoritm

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 23 februari 2022; kontroller kräver 8 redigeringar .

Dijkstras algoritm är en grafalgoritm som uppfanns av den holländska vetenskapsmannen Edsger Dijkstra 1959 . Hittar de kortaste vägarna från en av grafens hörn till alla andra. Algoritmen fungerar bara för grafer utan kanter med negativ vikt . Algoritmen används ofta i programmering, till exempel används den av routingprotokollen OSPF och IS-IS .

Problemformulering

Exempel

Alternativ 1. Med tanke på ett nätverk av vägar som förbinder städerna i Moskva-regionen. Vissa vägar är enkelriktade. Hitta de kortaste vägarna från stad A till varje stad i regionen (om du bara kan röra dig längs vägar).

Alternativ 2. Det finns ett antal flygningar mellan världens städer, kostnaden är känd för varje. Kostnaden för ett flyg från A till B kanske inte är lika med kostnaden för ett flyg från B till A. Hitta den lägsta kostnadsrutten (eventuellt med transfers) från Köpenhamn till Barnaul .

Formell definition

Givet en vägd riktad [1] graf utan bågar med negativ vikt [2] . Hitta de kortaste vägarna från någon hörn av grafen till alla andra hörn i denna graf. $G(V,E)$ $a$ $G$

Informell förklaring

Varje vertex från V tilldelas en etikett — det minsta kända avståndet från denna vertex till en .

Algoritmen fungerar steg för steg - vid varje steg "besöker" den en vertex och försöker reducera etiketter.

Algoritmen avslutas när alla hörn har besökts.

Initiering .

Etiketten för själva vertex a antas vara 0, etiketterna för de andra hörnen är inställda på oändligt.

Detta återspeglar att avstånden från a till andra hörn ännu inte är kända.

Alla hörn i grafen är markerade som obesökta.

Algoritm steg .

Om alla hörn har besökts avslutas algoritmen.

Annars, från de hörn som ännu inte har besökts, väljs hörn u med minimietiketten.

Vi överväger alla möjliga rutter där u är den näst sista punkten. De hörn som kanterna från u leder till kallas grannarna till denna vertex. För varje granne till u , förutom de som är markerade som besökta, överväg en ny väglängd som är lika med summan av värdena för den aktuella etiketten u och längden på kanten som förbinder u med denna granne.

Om det mottagna längdvärdet är mindre än etikettvärdet för grannen, ersätt etikettvärdet med det erhållna längdvärdet. Efter att ha övervägt alla grannar markerar vi vertex u som besökt och upprepar steget i algoritmen .

Exempel

Betrakta exekveringen av algoritmen i exemplet på grafen som visas i figuren.

Låt det krävas att hitta de kortaste avstånden från 1:a vertex till alla andra.

Cirklarna indikerar hörn, linjerna indikerar banorna mellan dem (grafens kanter).

Antalet hörn anges i cirklarna, deras vikt anges ovanför kanterna - banans längd.

Bredvid varje vertex är en röd etikett markerad - längden på den kortaste vägen till denna vertex från vertex 1.

Första steget .

Vertex 1 har minimietiketten. Vertices 2, 3 och 6 är dess grannar.

Den första granne till vertex 1 är i sin tur vertex 2, eftersom längden på vägen dit är minimal.

Längden på vägen till den genom vertex 1 är lika med summan av värdet på etiketten för vertex 1 och längden på kanten som går från 1:a till 2:a, det vill säga 0 + 7 = 7.

Detta är mindre än den nuvarande etiketten för vertex 2, oändlighet, så den nya etiketten för den 2:a vertexen är 7.

Vi utför en liknande operation med två andra grannar till den 1: a vertexen - den 3: e och 6: e.

Alla grannar till nod 1 är kontrollerade.

Det nuvarande minimiavståndet till topp 1 anses vara slutgiltigt och kan inte revideras.

Kryssa över det i grafen för att markera att denna vertex har besökts.

Andra steget .

Återigen hittar vi det "närmaste" av de obesökta hörnen. Detta är vertex 2 märkt 7.

Återigen försöker vi minska beteckningarna för grannarna till den valda vertexen, och försöker passera genom dem genom den 2: a vertexen. Vertex 2:s grannar är hörn 1, 3 och 4.

Den första (i ordning) granne till vertex 2 är vertex 1. Men den har redan besökts, så vi gör ingenting med den 1: a vertexen.

Nästa granne är vertex 3, eftersom den har minimietiketten.

Om du går till den genom 2, kommer längden på en sådan väg att vara lika med 17 (7 + 10 = 17). Men den nuvarande etiketten för den tredje vertexen är 9, vilket är mindre än 17, så etiketten ändras inte.

En annan granne till vertex 2 är vertex 4.

Om du går till den genom den 2:a, kommer längden på en sådan väg att vara lika med summan av det kortaste avståndet till den 2:a vertexen och avståndet mellan hörn 2 och 4, det vill säga 22 (7 + 15 = 22) .

Sedan 22< sätter vi etiketten för vertex 4 till 22. $\infty$

Alla grannar till vertex 2 har setts, vi fryser avståndet till det och markerar det som besökt.

Tredje steget .

Vi upprepar steget i algoritmen genom att välja vertex 3. Efter dess "bearbetning" får vi följande resultat:

Nästa steg .

Vi upprepar steget i algoritmen för de återstående hörnen. Dessa kommer att vara hörn 6, 4 respektive 5.

Slutförande av algoritmexekveringen .

Algoritmen avslutas när alla hörn har besökts.

Resultatet av algoritmen är synligt i den sista figuren: den kortaste vägen från vertex 1 till 2 är 7, till 3 är 9, till 4 är 20, till 5 är 20, till 6 är 11.

Om vid något tillfälle alla obesökta hörn är markerade med oändlighet, betyder det att dessa hörn inte kan nås (det vill säga att grafen inte är ansluten ). Då kan algoritmen slutföras före schemat.

Algoritm

Notation

$V$ är uppsättningen av grafens hörn
$E$ är uppsättningen av grafkanter
$w[ij]$ - vikt (längd) på revbenet $I j$
$a$ - spetsen, från vilken avstånden söks
$U$ - uppsättning besökta hörn
$d[u]$ — i slutet av algoritmen är lika med längden på den kortaste vägen från toppen $a$ $u$
$p[u]$ — i slutet av algoritmen innehåller den kortaste vägen från till $a$ $u$
$v$ är det aktuella hörnet som beaktas av algoritmen

Algoritmimplementeringskod

Nedan finns koden för att implementera algoritmen i programmeringsspråket Java . Detta implementeringsalternativ är inte det bästa, men visar tydligt den möjliga implementeringen av algoritmen:

klass Dijkstra { dubbel [] dist = ny dubbel [ GV () ] ; Edge [] pred = new Edge [ GV () ] ; public Dijkstra ( WeightedDigraph G , int s ) { boolean [] markerad = new boolean [ GV () ] ; för ( int v = 0 ; v < GV ( ); v ++ ) dist [ v ] = Dubbel . POSITIVE_INFINITY ; MinPQplus < Double , Integer > pq ; pq = new MinPQplus < Double , Integer > (); \\ Prioritetskö _ dist [ s ] = 0,0 ; pq . sätta ( dist [ s ] , s ); while ( ! pq . isEmpty ()) { intv = pq . _ delmin (); if ( markerad [ v ] ) fortsätt ; markerad ( v ) = sant ; för ( Edge e ( v )) { int w = e . till (); if ( dist [ w ]> dist [ v ] + e . vikt ()) { dist [ w ] = dist [ v ] + e . vikt (); pred [ w ] = e ; pq . infoga ( dist [ w ] , w ); } } } } }

Pseudokod

Tilldela

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

För alla andra än , tilldelar vi . $u\in V$ $a$ $d[u]\blir\infty$

Hejdå . Låta vara en vertex med minimum $\exists v\notin U$ $v\notin U$ $d[v]$ $v$ $U$

För alla som $u\notin U$ $vu\in E$

om då $d[u]>d[v]+w[vu]$

förändra $d[u]\får d[v]+w[vu]$

förändra $p[u]\gets (p[v],u)$

Beskrivning

I den enklaste implementeringen kan en array av tal användas för att lagra talen d [ i ], och en array av booleska variabler kan användas för att lagra medlemskapet av ett element i mängden U.

I början av algoritmen antas avståndet för den initiala vertexen vara noll, och alla andra avstånd fylls med ett stort positivt tal (större än den maximalt möjliga vägen i grafen ). Flaggarrayen är fylld med nollor. Sedan startar huvudslingan.

Vid varje steg i slingan letar vi efter en vertex med ett minsta avstånd och en flagga lika med noll. Sedan sätter vi flaggan till 1 i den och kontrollerar alla hörn intill den . Om avståndet i dem (i ) är större än summan av avståndet till den aktuella vertexen och längden på kanten, så minskar vi det. Slingan slutar när flaggorna för alla hörn blir lika med 1, eller när alla hörn med flaggan är 0 . Det senare fallet är möjligt om och endast om grafen G är bortkopplad. $v$ $u$ $u$ $d[i]=\infty$

Bevis på riktighet

Låta vara längden på den kortaste vägen från vertex till vertex . Låt oss bevisa genom induktion att jämlikheten gäller vid det ögonblick då vi besöker någon vertex . $l(v)$ $a$ $v$ $z$ $d(z)=l(z)$

Bas. Toppunkten besöks först . I det här ögonblicket . $a$ $d(a)=l(a)=0$

Steg. Låt oss säga att vi har valt en topp att besöka . Låt oss bevisa det i detta ögonblick . Till att börja med noterar vi att för alla hörn det alltid gäller (algoritmen kan inte hitta en väg som är kortare än den kortaste av alla befintliga). Låt vara den kortaste vägen från till . Toppen är på och inte besökt. Därför är uppsättningen av obesökta hörn inte tom. Låt vara den första obesökta hörn på , och vara den som föregår den (därav besökt). Eftersom vägen är den kortaste, är den del som leder från genom till också den kortaste, därför . $z\neq a$ $d(z)=l(z)$ $v$ $d(v)\geq l(v)$ $P$ $a$ $z$ $z$ $P$ $P$ $y$ $P$ $x$ $P$ $a$ $x$ $y$ $l(y)=l(x)+w(xy)$

Genom induktionshypotesen, vid ögonblicket för att besöka vertexet , Därför fick vertexet en etikett som inte var större än . Därför, . Om , då är induktionssteget bevisat. Annars, eftersom vertex för närvarande är valt och inte , är etiketten minimal bland de obesökta, det vill säga . Genom att kombinera detta med , har vi , vilket skulle bevisas. $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)$

Eftersom algoritmen avslutas när alla hörn har besökts, i det ögonblicket för alla hörn. $d=l$

Algoritmens komplexitet

Komplexiteten hos Dijkstras algoritm beror på hur vertex v hittas , hur uppsättningen av obesökta hörn lagras och hur etiketterna uppdateras. Beteckna med n antalet hörn och med m antalet kanter i grafen G .

I det enklaste fallet, när hela uppsättningen av hörn genomsöks för att hitta vertex med minimum d [ v ], och en array används för att lagra värdena för d , är algoritmens gångtid . Huvudslingan exekveras cirka n gånger, i var och en av dem spenderas cirka n operationer på att hitta minimum. Att cykla genom grannarna till varje besökt vertex tar ett antal operationer proportionellt mot antalet kanter m (eftersom varje kant inträffar exakt två gånger i dessa cykler och kräver ett konstant antal operationer). Således är den totala körtiden för algoritmen , men eftersom , är det . $O(n^{2})$ $O(n^{2}+m)$ $m\leq n(n-1)$ $O(n^{2})$

För glesa grafer (det vill säga de för vilka m är mycket mindre än n²) kan obesökta hörn lagras i en binär hög , och värdena för d [ i ] kan användas som en nyckel, sedan tiden att ta bort en vertex från blir medan modifieringstiden ökar till . Eftersom slingan exekveras cirka n gånger, och antalet etikettändringar inte är mer än m , är körtiden för en sådan implementering . $\överlinje U$ $\log n$ $d[i]$ $\log n$ $O(n\log n+m\log n)$

Om vi använder en Fibonacci-hög för att lagra obesökta hörn , för vilka raderingen sker i genomsnitt för , och värdet minskar i genomsnitt för , så kommer algoritmens körtid att vara . Men enligt föreläsningarna av Alekseev och Talanov [3] : $O(\log n)$ $O(1)$ $O(n\log n+m)$

de dolda konstanterna i de asymptotiska kostnadsuppskattningarna är stora, och användningen av Fibonacci-högar är sällan lämplig: vanliga binära ( d-ary ) högar är mer effektiva i praktiken.

Alternativ till dem är tjocka högar, tunna högar och Brodalshögar , som har samma asymptotiska uppskattningar, men mindre konstanter [4] .

Se även

Länkar

C. Anisimov. Hur man bygger den kortaste vägen mellan två punkter.
Implementering av den enklaste versionen av Dijkstras algoritm på e-maxx.ru
Implementering av en variant av Dijkstras algoritm för glesa grafer på e-maxx.ru
Implementering av en variant av Dijkstras algoritm med en rotheuristik
Dijkstras algoritm. Programkod i Python
Exempel på YouTube
Dijkstras algoritm - implementering av algoritmen på olika språk på Rosetta Code .

Litteratur

Dijkstra E. W. En anteckning om två problem i samband med grafer // Numer . Math / F. Brezzi - Springer Science + Business Media , 1959. - Vol. 1, Iss. 1. - P. 269-271. — ISSN 0029-599X ; 0945-3245 - doi:10.1007/BF01386390
Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmer: konstruktion och analys = Introduktion till algoritmer. - 2:a uppl. - M .: "Williams" , 2006. - S. 1296. - ISBN 0-07-013151-1 .
Levitin A. V. Kapitel 9. Giriga metoder: Dijkstras algoritm // Algoritmer. Introduktion till utveckling och analys - M . : Williams , 2006. - S. 189-195. — 576 sid. — ISBN 978-5-8459-0987-9

Anteckningar

↑ Speciella fall av en riktad graf är oriktade och blandade ("partiellt riktade") grafer.
↑ För en graf med negativa vikter används en mer generell algoritm - Dijkstra's Algorithm with Potentials
↑ Vladimir Alekseev, Vladimir Talanov, Kurs "Datastrukturer och beräkningsmodeller", Föreläsning nr 7: Binomial and Fibonacci Heaps // 09/26/2006, Intuit.ru
↑ Vladimir Alekseev, Vladimir Talanov, Kurs "Datastrukturer och beräkningsmodeller", Föreläsning nr 8: Tunna högar // 09/26/2006, Intuit.ru

Algoritmer för grafsökning
Oinformerade metoder	Dubbelriktad sökning Strålsökning Lexikografisk bredd första sökning Utöka första sökningen Sök efter kostnadskriterium Djup första sökning Backtracking sökning Sök genom att klättra till toppen Djupbegränsad sökning Djup-första sökning med iterativ fördjupning
Informerade metoder	Alfa beta-klippning Gren och bunden metod Sök efter första bästa matchning A* B* D* Att hitta en övergångspunkt IDA* Rekursiv sökning på den första bästa matchningen SMA*
Genvägar	Vågalgoritm Bellman-Ford algoritm Dijkstras algoritm Johnsons algoritm Levits algoritm Floyd-Warshall algoritm Kantsökning
Minsta spännträd	Boruvkas algoritm Prims algoritm Kruskals algoritm
Övrig	British Museum Algoritm Edmonds algoritm Trädpassering Algoritmen för närmaste granne i problemet med resande säljare