Î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.

Citește mai departe