Algoritmul Floyd–Warshall

Atlasele rutiere vechi aveau la final un tabel: distanța dintre fiecare pereche de orașe. Floyd–Warshall este o metodă de a calcula un astfel de tabel și unul dintre cei mai scurți algoritmi scriși vreodată: trei bucle, o comparație și fiecare distanță minimă își găsește locul.

Un graf mic ale cărui muchii au lungimi, lângă un tabel cu distanțele dintre fiecare pereche de noduri, cu un rând și o coloană evidențiate
Un graf mic ale cărui muchii au lungimi, lângă un tabel cu distanțele dintre fiecare pereche de noduri, cu un rând și o coloană evidențiate

Ideea

Algoritmul lui Dijkstra și Bellman–Ford găsesc distanțele minime de la un singur start. Floyd–Warshall le găsește dintr-odată de la fiecare nod la fiecare alt nod, într-un tabel cu un rând și o coloană pentru fiecare nod. Pornește de la ce spun direct muchiile, apoi îmbunătățește tot tabelul, permițând tot mai multe noduri ca noduri intermediare pe drum.

Pas cu pas

Completați tabelul: 0 de la fiecare nod la el însuși, lungimea muchiei între vecini și infinit în rest. Apoi, pentru fiecare nod k și pentru fiecare pereche i, j: dacă distanța de la i la k plus distanța de la k la j este mai mică decât distanța de la i la j, scrieți numărul mai mic. Acesta este tot algoritmul. În cod sunt trei bucle, cu k în exterior.

Un exemplu

Luați patru noduri cu muchiile A–B de lungime 3, B–C 1, A–C 5 și C–D 2. Tabelul pornește cu acestea și cu infinit pentru A–D și B–D. Runda A nu schimbă nimic, pentru că orice drum prin A este mai lung. Runda B găsește drumul de la A la C prin B: 3 + 1 = 4, mai mic decât 5. Runda C găsește drumul de la A la D prin C: 4 + 2 = 6 și de la B la D: 1 + 2 = 3, ambele primele găsite. Runda D nu schimbă nimic. Tabelul final: A–B 3, A–C 4, A–D 6, B–C 1, B–D 3, C–D 2.

De ce contează ordinea buclelor

Nodul intermediar k trebuie să fie bucla exterioară. După runda lui k, fiecare celulă este cea mai scurtă distanță folosind ca noduri intermediare doar primele k noduri, iar runda următoare se sprijină pe asta: cel mai bun drum prin noul nod intermediar este cel mai bun drum până la el plus cel mai bun drum de la el, iar ambele sunt deja corecte. Dacă puneți k într-o buclă interioară, garanția se pierde și pot rămâne distanțe greșite. Actualizarea tabelului pe loc în timpul unei runde este sigură, pentru că rândul și coloana lui k nu se schimbă în acea rundă.

Istorie și utilizări

Bernard Roy a descris metoda în 1959. În 1962, Stephen Warshall a publicat-o pentru închiderea tranzitivă, care întreabă doar dacă un nod poate ajunge la altul, iar Robert Floyd a publicat-o pentru drumuri minime. Ea calculează tabele de distanțe și tabele de rutare, găsește diametrul unei rețele, arată ce noduri pot ajunge la care și, printr-o celulă negativă pe diagonală, dezvăluie un ciclu negativ.

Explorați

Deschideți aplicația și apăsați Pas. Graful este într-o parte, iar tabelul în cealaltă. Fiecare rundă evidențiază rândul și coloana nodului intermediar curent; fiecare pas scrie distanța mai scurtă a unei perechi și încadrează cele două celule care au fost adunate. Celulele modificate în această rundă sunt colorate. Alegeți un start și o țintă ca să vedeți cel mai scurt drum dintre ele când tabelul este complet.

Întrebări frecvente

Care este complexitatea în timp a algoritmului Floyd–Warshall?

O(n³) pentru n noduri, indiferent de numărul de muchii, și O(n²) memorie pentru tabel. Este metoda preferată pentru grafuri mici sau dense, unde bucla sa simplă rulează foarte repede.

Floyd–Warshall sau Dijkstra din fiecare nod?

Pentru un graf dens sau când muchiile pot fi negative, Floyd–Warshall este mai simplu și aproximativ la fel de rapid. Pentru un graf mare și rar, fără muchii negative, e mai rapid să rulați algoritmul lui Dijkstra din fiecare nod.

Este Floyd–Warshall programare dinamică?

Da. Rezolvă problema pentru drumuri cu noduri intermediare printre primele k noduri folosind răspunsurile pentru primele k − 1 noduri și păstrează un singur tabel, pe care îl suprascrie pe parcurs.

Ce este închiderea tranzitivă?

Tabelul cu nodurile care pot ajunge la alte noduri, fără distanțe. Versiunea lui Warshall a algoritmului o calculează cu "sau" și "și" în loc de "min" și "+".

Ești gata să încerci?

Deschide PictorX în browser – fără instalare și fără card de credit.

Încercați Floyd–Warshall