Algoritmul Johnson

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 7 noiembrie 2019; verificarea necesită 1 editare .

Algoritmul lui Johnson - vă permite să găsiți cele mai scurte căi între toate perechile de vârfuri într-un grafic direcționat ponderat . Acest algoritm funcționează dacă graficul conține muchii cu greutate pozitivă sau negativă, dar nu există cicluri cu greutate negativă. Numit după D. B. Johnson , care a publicat algoritmul în 1977.

Algoritm

Dat un grafic cu o funcție de greutate . Dacă ponderile tuturor muchiilor dintr-un grafic sunt nenegative, puteți găsi cele mai scurte căi între toate perechile de vârfuri rulând algoritmul lui Dijkstra o dată pentru fiecare vârf. Dacă graficul conține muchii cu greutăți negative, dar nu există cicluri cu greutăți negative, se poate calcula un nou set de muchii cu greutăți nenegative, permițând utilizarea metodei anterioare. Noul set constând din greutăți de margine trebuie să îndeplinească următoarele proprietăți. $G=(V,E)$ $\omega \colon E\la R$ $\omega$ ${\pălărie {\omega ))$

Pentru toate marginile , noua greutate este de . $(u,\;v)$ ${\hat {\omega }}(u,\;v)>0$
Pentru toate perechile de vârfuri , calea este cea mai scurtă cale de la vârf la vârf folosind funcția de greutate dacă și numai dacă este și cea mai scurtă cale de la vârf la vârf cu funcția de pondere . $u,\;v\în V$ $p$ $u$ $v$ $\omega$ $p$ $u$ $v$ ${\pălărie {\omega ))$

Păstrarea celor mai scurte căi

Lema (Schimbarea greutăților păstrează cele mai scurte căi). Fie un grafic direcționat ponderat cu o funcție de pondere și fie o funcție arbitrară care mapează vârfurile la numere reale. Pentru fiecare muchie o definim $G=(V,\;E)$ $\omega \colon E\la R$ $h\colon V\la R$ $(u,\;v)\în E$

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

Fie o cale arbitrară de la vârf la vârf . este calea cea mai scurtă cu funcția de greutate dacă și numai dacă este calea cea mai scurtă cu funcția de greutate , adică egalitatea este echivalentă cu egalitatea . În plus, un grafic conține un ciclu cu o pondere negativă folosind o funcție de pondere dacă și numai dacă conține un ciclu cu o pondere negativă folosind o funcție de pondere . $p=\langle v_{0},\;v_{1},\;\ldots ,\;v_{k}\rangle$ $v_{0}$ $v_{k}$ $p$ $\omega$ ${\pălărie {\omega ))$ $\omega (p)=\delta (v_{0},\;v_{k})$ ${\hat {\omega }}(p)={\hat {\delta }}(v_{0},\;v_{k})$ $G$ $\omega$ ${\pălărie {\omega ))$

Modificarea greutății

Pentru acest grafic, creați un nou grafic , unde , pentru un vârf nou și . $G'=(V',\;E')$ $V'=V\cup \{s\}$ $s\nu \în V$ $E'=E\cup \{(s,\;v):v\in V\}$
Să extindem funcția de greutate în așa fel încât egalitatea să fie valabilă pentru toate vârfurile . $\omega$ $v\în V$ $\omega (s,\;v)=0$
În continuare, definim pentru toate nodurile valoarea și noi ponderi pentru toate muchiile . $v\in V'$ $h(v)=\delta (s,\;v)$ ${\hat {\omega }}(u,\;v)=\omega (u,\;v)+h(u)-h(v)\geqslant 0$

Procedura de bază

Algoritmul lui Johnson folosește algoritmul Bellman-Ford și algoritmul lui Dijkstra , implementate ca subrutine. Muchiile sunt stocate ca liste de vârfuri adiacente. Algoritmul returnează o matrice obișnuită de dimensiune , unde , sau dă un mesaj că graficul de intrare conține un ciclu cu o pondere negativă. $D=d_{ij}$ $|V|\times |V|$ $d_{ij}=\delta(i,\;j)$

Algoritmul lui Johnson Construiți un grafic dacă Bellman_Ford = FALSE apoi imprimați „ Graful de intrare conține un ciclu cu o greutate negativă” returnați ø pentru fiecare setați valoarea la ,

G'

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

v\in V'

h(v)

\delta (s,\;v)

calculate de algoritmul Bellman-Ford pentru fiecare muchie face pentru pentru fiecare vârf , algoritmul lui Dijkstra calculează valori pentru toate vârfurile pentru fiecare vârf nu returnează D

(u,\;v)\in E'

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

u\în V

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

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

v\în V

v\în V

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

Dificultate

Dacă coada cu prioritate nedescrescătoare din algoritmul lui Dijkstra este implementată ca un heap Fibonacci , atunci timpul de rulare al algoritmului lui Johnson este . Cu o implementare mai simplă a unei cozi cu prioritate nedescrescătoare, timpul de rulare devine egal cu , dar pentru graficele rare, această valoare din limita asimptotică se comportă mai bine decât timpul de rulare al algoritmului Floyd-Warshall . $O(V^{2}\log V+VE)$ $O(VE\log V)$

Vezi și

Link -uri

Algoritm Vizualizator

Literatură

Thomas H. Kormen et al.Algoritmi : construcție și analiză. - Ed. a II-a. - M . : Editura Williams , 2007. - S. 726. - ISBN 5-8459-0857-4 .
Thomas H. Kormen et al.Algoritmi : construcție și analiză. - Ed. 1. - M .: MTSNMO , 2004. - S. 523. - ISBN 5-900916-37-5 .

Algoritmi de căutare grafică
Metode neinformate	Căutare bidirecțională Căutare fascicul Prima căutare a lățimii lexicografice Lățimea prima căutare Căutare după criteriul de cost Profunzime prima căutare Căutare înapoi Caută prin urcare în vârf Căutare limitată la profunzime Căutare în profunzime cu aprofundare iterativă
Metode informate	Decuparea alfa beta Ramura și metoda legată Căutați după prima potrivire A* B* D* Găsirea unui punct de tranziție IDA* Căutare recurstivă pe primul cel mai bun meci SMA*
Comenzi rapide	Algoritmul undelor Algoritmul Bellman-Ford algoritmul lui Dijkstra Algoritmul Johnson algoritmul lui Levit Algoritmul Floyd-Warshall Căutare margine
Arborele de întindere minim	algoritmul lui Boruvka algoritmul lui Prim algoritmul lui Kruskal
Alte	Algoritmul British Museum Algoritmul Edmonds Traversarea copacilor Algoritmul celui mai apropiat vecin în problema vânzătorului ambulant