În jurul anului 1960 a fost descoperit un algoritm pentru drumuri în grafuri orientate. Descoperirea a fost făcută independent de către trei oameni de stiință în domeniul algoritmilor: Robert Floyd, Bernard Roy și Stephen Warshall.
Algoritmul se regăsește sub diferite denumiri care conțin numele descoperitorilor, este bazat pe programarea dinamică și poate fi utilizat în următoarele două moduri:
- pentru un graf orientat oarecare determină matricea drumurilor – stabilește despre oricare două noduri
x y dacă există drum de la x la y – este de regulă cunoscut sub numele Roy-Warshal
- pentru un graf orientat ponderat (cu costuri) – determină pentru fiecare pereche de noduri costul minim al unui drum cu extremitățile în acele noduri – este de regulă cunoscut sub numele Roy-Floyd
Ambele variante permit și reconstituirea unor drumuri între două noduri date.
Candale Silviu (silviu)