Algoritmul Bellman-Ford

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 20 februarie 2019; verificările necesită 6 modificări .

Algoritmul Bellman-Ford

Numit după	Richard Bellman și Ford, Lester
Autor	Richard Bellman , Ford, Lester și Edward Forest Moore
scop	găsirea celui mai scurt drum într-un grafic
Structură de date	grafic
cel mai rău moment	$\Theta (\|V\|\|E\|)$
Cel mai bun timp	$\Theta (\|E\|)$
Costul memoriei	$\Theta (\|V\|)$
Fișiere media la Wikimedia Commons

Algoritmul Bellman-Ford este un algoritm pentru găsirea celei mai scurte căi într-un grafic ponderat . În timp, algoritmul găsește cele mai scurte căi de la un vârf al graficului la toate celelalte. Spre deosebire de algoritmul lui Dijkstra , algoritmul Bellman-Ford permite margini cu greutăți negative . Propus independent de Richard Bellman și Lester Ford . Favorizat de Sirius. $O(|V|\cdot |E|)$

Algoritmul de rutare RIP (algoritmul Bellman-Ford) a fost dezvoltat pentru prima dată în 1969 ca bază pentru ARPANET .

Declarația problemei

Dat un grafic direcționat sau nedirecționat cu muchii ponderate. Lungimea unei căi este suma greutăților muchiilor incluse în această cale. Este necesar să găsiți cele mai scurte căi de la vârful selectat la toate vârfurile graficului. $G$ $s$

Rețineți că cele mai scurte căi este posibil să nu existe. Deci, într-un grafic care conține un ciclu cu o greutate totală negativă, există o cale arbitrar scurtă de la un vârf al acestui ciclu la altul (fiecare rundă a ciclului reduce lungimea căii). Un ciclu a cărui sumă a greutății muchiilor este negativă se numește ciclu negativ .

Rezolvarea unei probleme pe un grafic fără cicluri negative

Să rezolvăm problema dată pe un grafic, în care în mod evident nu există cicluri negative.

Pentru a găsi cele mai scurte căi de la un vârf la toate celelalte, folosim metoda de programare dinamică . Să construim o matrice ale cărei elemente vor denota următoarele: este lungimea celei mai scurte căi de la până la care nu conține mai mult decât muchii. $A_{{ij}}$ $a_{{ij}}$ $s$ $i$ $j$

O cale care conține 0 muchii există doar până la vârf . Astfel, este egal cu 0 dacă și în caz contrar. $s$ $A_{i0)$ $i=s$ $+\infty$

Acum luați în considerare toate căile de la până la care conțin exact margini. Fiecare astfel de cale este o cale de la marginea la care se adaugă ultima margine. Dacă toate datele despre căile de lungime au fost deja calculate, atunci nu este dificil să determinați a treia coloană a matricei. $s$ $i$ $j$ $j-1$ $j-1$ $j$

Iată cum arată algoritmul pentru găsirea lungimilor celor mai scurte căi dintr-un grafic fără cicluri negative:

pentru a face pentru a face pentru dacă apoi întoarce

v\în V

d[v]\gets +\infty

d[s]\ obține 0

primesc 1

|V|-1

(u,v)\în E

d[v]>d[u]+w(u,v)

d[v]\obține d[u]+w(u,v)

d

Iată setul de vârfuri ale graficului , este mulțimea muchiilor acestuia și este o funcție de greutate definită pe marginile graficului (returnează lungimea arcului care duce de la vârf la ), este o matrice care conține distanțe de la vârful la orice alt vârf. $V$ $G$ $E$ $w$ $u$ $v$ $d$ $s$

Bucla exterioară este executată o dată, deoarece calea cea mai scurtă nu poate conține mai multe margini, altfel va conține o buclă care poate fi cu siguranță aruncată. $|V|-1$

În loc de o matrice , puteți stoca întreaga matrice , dar aceasta necesită memorie. Dar, în același timp, puteți calcula singuri cele mai scurte căi, și nu doar lungimile lor. Pentru a face acest lucru, vom crea o matrice . $d$ $A$ $O(V^{2})$ $P_{ij}$

Dacă elementul conține lungimea celei mai scurte căi de la până la muchiile care le conține , atunci conține vârful anterior până la una dintre aceste căi cele mai scurte (pot fi mai multe dintre ele). $A_{{ij}}$ $s$ $i$ $j$ $P_{ij}$ $i$

Acum algoritmul Bellman-Ford arată astfel:

pentru pentru a face pentru a face pentru dacă atunci

v\în V

primesc 0

|V|-1

A_{{vi}}\obține +\infty

A_{{s0}}\obține 0

primesc 1

|V|-1

(u,v)\în E

A_{{vi}}>A_{{u,i-1}}+w(u,v)

A_{{vi}}\obține A_{{u,i-1}}+w(u,v)

P_{{vi}}\ te primește

După executarea acestui algoritm, elementele conțin lungimile celor mai scurte căi de la până la cu numărul de muchii , iar dintre toate astfel de căi, ar trebui să fie aleasă cea mai scurtă. Și cea mai scurtă cale către vârful cu margini este restaurată după cum urmează: $A_{{i,j}}$ $s$ $i$ $j$ $i$ $j$

în timp ce retur p

j>0

p[j]\obține i

i\obține P_{{ij}}

j\ obține j-1

Un grafic cu cicluri negative

Algoritmul Bellman-Ford face foarte ușor să se determine dacă există un ciclu negativ într-un grafic care este accesibil de la vârf . Este suficient să efectuați o iterație exterioară a buclei nu , ci exact o dată. Dacă în timpul execuției ultimei iterații lungimea celei mai scurte căi către orice vârf a scăzut strict, atunci graficul are un ciclu negativ accesibil de la . Pe baza acesteia, putem propune următoarea optimizare: urmăriți modificările din grafic și, de îndată ce acestea se termină, ieșiți din buclă (iterațiile ulterioare vor fi lipsite de sens). $G$ $s$ $|V|-1$ $|V|$ $s$

Literatură

R. Bellman: Despre o problemă de rutare // Quarterly of Applied Mathematics. 1958. Vol 16, nr. 1. C. 87-90, 1958.
LR Ford, Jr., DR Fulkerson. Fluxuri în rețele, Princeton University Press, 1962.

Vezi și

Link -uri

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