Nod intermediar
Perechi scurtate
Perechi verificate

  • Nodul intermediar curent
  • Deja nod intermediar
  • Pereche scurtată
  • Drum
Un clic pe un nod setează

Mai multe despre algoritmul Floyd–Warshall

Algoritmul Floyd–Warshall

Cât de departe este fiecare oraș de fiecare alt oraș? Floyd–Warshall răspunde dintr-odată, cu un tabel și trei bucle imbricate. Fiecare rundă permite încă un nod ca nod intermediar pe drum și verifică, pentru fiecare pereche, dacă ocolul prin el este mai scurt. Avansați pas cu pas ca să vedeți cum se completează tabelul și cum scad distanțele. Apăsați Redare pentru a urmări cum se completează tabelul sau folosiți Pas și Înapoi pentru a avansa câte un pas. Trageți glisorul pentru pași pentru a sări oriunde. Tabelul conține cea mai scurtă distanță găsită până acum între fiecare pereche de noduri; numărul de pe fiecare muchie este lungimea ei. Fiecare rundă permite încă un nod ca nod intermediar pe drum, iar fiecare pas arată o pereche care devine mai scurtă prin el. Faceți clic pe un nod ca să devină start; comutați clicul pe Țintă și faceți clic pe alt nod ca să vedeți la final cel mai scurt drum dintre ele. Graf nou creează alt graf; alegeți câte noduri și muchii are. Cu tabla selectată, tastele săgeți avansează pas cu pas, bara de spațiu pornește și oprește redarea, iar Home și End sar la început și la sfârșit.

Cum funcționează

  1. Apăsați Redare sau folosiți Pas și Înapoi pentru a avansa câte un pas. Trageți glisorul pentru pași pentru a sări oriunde.
  2. Urmăriți tabelul: rândul și coloana nodului intermediar curent sunt colorate, iar fiecare pas scrie o distanță mai scurtă.
  3. Alegeți un start și o țintă ca să vedeți la final cel mai scurt drum dintre ele. Graf nou creează alt graf de încercat.

Cum funcționează Floyd–Warshall

Faceți un tabel cu un rând și o coloană pentru fiecare nod. Scrieți 0 pe diagonală, lungimea muchiei acolo unde două noduri sunt legate și infinit în rest. Apoi luați pe rând fiecare nod k ca posibil nod intermediar. Pentru fiecare pereche i, j, comparați distanța de la i la j din tabel cu distanța de la i la k plus distanța de la k la j și păstrați-o pe cea mai mică. După ultimul nod, fiecare celulă este cea mai scurtă distanță dintre cele două noduri ale ei.

De ce funcționează

După runda lui k, tabelul conține, pentru fiecare pereche, cel mai scurt drum ale cărui noduri intermediare se află toate printre nodurile tratate până atunci. Runda următorului nod trebuie doar să decidă dacă acel nod ajută: un drum minim prin el este un drum minim până la el plus un drum minim de la el, iar ambele sunt deja în tabel. Acest mod de a construi un răspuns mare din răspunsuri mai mici, deja găsite, se numește programare dinamică. Cu muchii negative funcționează în continuare, iar un număr negativ pe diagonală dezvăluie un ciclu negativ.

Întrebări frecvente

Ce este algoritmul Floyd–Warshall?

Un algoritm care găsește cea mai scurtă distanță dintre fiecare pereche de noduri într-un graf ponderat. Păstrează un tabel cu distanțe și, pentru fiecare nod pe rând, verifică dacă trecerea prin acel nod scurtează vreo pereche.

Cât de rapid este Floyd–Warshall?

Are trei bucle imbricate peste cele n noduri, deci munca crește cu n³, iar tabelul are nevoie de n² celule. Este în regulă pentru grafuri cu câteva sute de noduri. Pentru grafuri mari și rare, e mai rapid să rulați algoritmul lui Dijkstra din fiecare nod.

Poate Floyd–Warshall să lucreze cu muchii negative?

Da, cât timp nu există un ciclu negativ. Dacă există unul, o celulă de pe diagonală devine negativă, iar așa îl detectează Floyd–Warshall.

Cum obțin drumurile, nu doar distanțele?

Păstrați un al doilea tabel cu următorul nod de pe drumul de la i la j. Ori de câte ori o pereche devine mai scurtă prin k, copiați următorul nod de la i spre k. Urmând acest tabel de la i la j, obțineți drumul.

Este graful meu trimis undeva?

Nu. Graful este creat și tabelul este completat în browserul dumneavoastră, iar ultimele setări rămân în stocarea locală a acestui browser.

Ești gata să încerci?

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

Mergi la editor