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

Matricea drumurilor

Fie \( G=(V,U) \) un graf orientat cu \( n \) noduri. Algoritmul Roy-Warshall construiește matricea drumurilor: \( D \) cu \( n \) linii și \( n \) coloane, în care: …

Drumuri de cost minim într-un graf orientat

Fie \( G = (V, U) \) un graf orientat ponderat – în care fiecare arc are asociată o valoare reală numită pondere sau cost, de regulă pozitivă, cu noduri numerotate de la \( 1 \) la \( n \). …