Johnsons 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 7. november 2019; verifikation kræver 1 redigering .

Johnsons algoritme - giver dig mulighed for at finde de korteste veje mellem alle par af hjørner i en vægtet rettet graf . Denne algoritme virker, hvis grafen indeholder kanter med positiv eller negativ vægt, men der er ingen cyklusser med negativ vægt. Opkaldt efter D. B. Johnson , som udgav algoritmen i 1977.

Algoritme

Givet en graf med en vægtfunktion . Hvis vægten af alle kanter i en graf er ikke-negative, kan du finde de korteste veje mellem alle par af hjørner ved at køre Dijkstras algoritme én gang for hvert hjørne. Hvis grafen indeholder kanter med negative vægte, men ingen cyklusser med negative vægte, kan et nyt sæt kanter med ikke-negative vægte beregnes, så den tidligere metode kan bruges. Det nye sæt bestående af kantvægte skal opfylde følgende egenskaber. $G=(V,E)$ $\omega \colon E\to R$ $\omega$ ${\hat {\omega ))$

For alle kanter er den nye vægt . $(u,\;v)$ ${\hat {\omega }}(u,\;v)>0$
For alle par af toppunkter er stien den korteste vej fra toppunkt til toppunkt ved hjælp af vægtfunktionen, hvis og kun hvis også er den korteste vej fra toppunkt til toppunkt med vægtfunktionen . $u,\;v\in V$ $s$ $u$ $v$ $\omega$ $s$ $u$ $v$ ${\hat {\omega ))$

Bevarelse af korteste veje

Lemma (Ændring af vægt bevarer korteste veje). Lad være en vægtet rettet graf med en vægtfunktion , og lad være en vilkårlig funktion, der kortlægger hjørner til reelle tal. For hver kant vi definerer $G=(V,\;E)$ $\omega \colon E\to R$ $h\colon V\to R$ $(u,\;v)\i E$

{\hat {\omega }}(u,\;v)=\omega (u,\;v)+h(u)-h(v).

Lade være en vilkårlig vej fra toppunkt til toppunkt . er den korteste vej med vægtfunktionen, hvis og kun hvis det er den korteste vej med vægtfunktionen , dvs. lighed er ækvivalent med lighed . Derudover indeholder en graf en cyklus med negativ vægt ved hjælp af en vægtfunktion, hvis og kun hvis den indeholder en cyklus med negativ vægt ved hjælp af en vægtfunktion . $p=\langle v_{0},\;v_{1},\;\ldots ,\;v_{k}\rangle$ $v_{0}$ $v_{k}$ $s$ $\omega$ ${\hat {\omega ))$ $\omega (p)=\delta (v_{0},\;v_{k})$ ${\hat {\omega }}(p)={\hat {\delta }}(v_{0},\;v_{k})$ $G$ $\omega$ ${\hat {\omega ))$

Ændring i vægt

For denne graf skal du oprette en ny graf , hvor , for nogle nye toppunkter , og . $G'=(V',\;E')$ $V'=V\cup \{s\}$ $s\not \in V$ $E'=E\cup \{(s,\;v):v\in V\}$
Lad os udvide vægtfunktionen på en sådan måde, at ligheden gælder for alle hjørner . $\omega$ $v\in V$ $\omega (s,\;v)=0$
Dernæst definerer vi for alle hjørner værdien og nye vægte for alle kanter . $v\in V'$ $h(v)=\delta (s,\;v)$ ${\hat {\omega }}(u,\;v)=\omega (u,\;v)+h(u)-h(v)\geqslant 0$

Grundlæggende procedure

Johnsons algoritme bruger Bellman-Ford- algoritmen og Dijkstras algoritme , implementeret som underrutiner. Kanter gemmes som lister over tilstødende hjørner. Algoritmen returnerer en almindelig matrix med størrelse , hvor , eller giver en besked om, at inputgrafen indeholder en cyklus med negativ vægt. $D=d_{ij}$ $|V|\ gange |V|$ $d_{ij}=\delta(i,\;j)$

Johnson's Algorithm Byg en graf, hvis Bellman_Ford = FALSE , så udskriv " Inputgrafen indeholder en cyklus med negativ vægt" returner ø for for hvert sæt værdien til ,

G'

(G',\;\omega ,\;s)

v\in V'

h(v)

\delta (s,\;v)

beregnet af Bellman-Ford algoritmen for for hver kant gør for for hvert toppunkt beregner Dijkstras algoritme værdier for alle toppunkter for for hvert toppunkt returnerer D

(u,\;v)\i E'

{\hat {\omega }}(u,\;v)\venstrepil \omega (u,\;v)+h(u)-h(v)

u\i V

(G,\;{\hat {\omega )),\;u)

{\hat {\delta }}(u,\;v)

v\in V

v\in V

d_{uv}\leftarrow {\hat {\delta }}(u,\;v)+h(v)-h(u)

Sværhedsgrad

Hvis den ikke-faldende prioritetskø i Dijkstras algoritme er implementeret som en Fibonacci-heap , så er køretiden for Johnsons algoritme . Med en enklere implementering af en ikke-faldende prioritetskø bliver køretiden lig med , men for sparsomme grafer opfører denne værdi i den asymptotiske grænse sig bedre end køretiden for Floyd-Warshall-algoritmen . $O(V^{2}\log V+VE)$ $O(VE\log V)$

Se også

Litteratur

Thomas H. Kormen et al. Algoritmer: konstruktion og analyse. - 2. udg. - M . : Williams Publishing House , 2007. - S. 726. - ISBN 5-8459-0857-4 .
Thomas H. Kormen et al. Algoritmer: konstruktion og analyse. - 1. udg. - M .: MTSNMO , 2004. - S. 523. - ISBN 5-900916-37-5 .

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