startApasă „Pas înainte". Pe rând, luăm fiecare nod k ca intermediar: dacă există drum i → k și k → j, atunci există și drum i → j.
Graful orientat vrem matricea drumurilor (i → j?)
Stare algoritmul Roy-Warshall
Nod intermediar k –Drumuri noi adăugate 0
Înmulțirea la pasul curent –
Regula: d[i][j] = d[i][k] × d[k][j]. Înmulțirea e de fapt un ȘI logic:
1 × 1 = 1 (ambele drumuri există → apare drumul i → j), iar dacă vreunul e 0,
produsul e 0 (drumul nu se poate face prin k).
Matricea drumurilor d[ ][ ] pornește de la adiacență · se completează cu 1
linia / coloana lui kd[i][k] și d[k][j]drum nou (d[i][j]←1)
Algoritmul pseudocod și C++ · linia activă evidențiată
Pseudocod
Cod C++
Limbaj natural ce face pasul curent
start
Preferințe privind cookie-urile
Folosim cookie-uri pentru analiza traficului, doar cu acordul tău.
Poți accepta cookie-urile opționale sau poți continua doar cu cele necesare — simulatorul
funcționează la fel.