Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- ******Algoritmul lui Roy Warshall*****
- Algoritmul de determinare a matricei drumurilor.
- 1. Se citeste matricea de adiacenta a grafului;
- 2. Se verifia pentru fiecare nod intermediar (prin conventie nodul k). Daca exista drum intre nodul initial "i" si nodul final "j"; Un nod
- "k" este nod intermediar pentru nodurile "i" si "j" daca exista arc de la nodul initial "i" la nodul intermediar "k" si in acelasi timp
- exista arc de la nodul intermediar "k" la nodul "j". Nodurile "i" si "j" sunt distincte si nodul "k" este diferit de nodurile "i" si "j";
- Matricea de adiacenta Matricea drumurilor
- 0 1 0 0 0 1 " 1 2 3 4 5 6"
- 0 0 1 1 1 0 1 1 1 1 1 1 1
- 0 0 0 1 0 1 2 1 1 1 1 1 1
- 1 0 0 0 0 1 3 1 1 1 1 1 1
- 0 0 0 1 0 1 4 1 1 1 1 1 1
- 0 0 0 0 0 0 5 1 1 1 1 1 1
- 6 0 0 0 0 0 0
- "
- */
- #include <fstream>
- using namespace std;
- ifstream f("matrice.in");
- ofstream g("matrice.out");
- int a[50][50],n,i,j,k;
- void citire()
- {
- f>>n;
- for(i=1; i<=n; i++)
- for(j=1; j<=n; j++)
- f>>a[i][j];
- }
- void Roy_Warshall()
- {
- for(k=1; k<=n; k++)
- for(i=1; i<=n; i++)
- for(j=1; j<=n; j++)
- if(a[i][j]==0 && k!=i && k!=j)
- a[i][j]=a[i][k]*a[j][k];
- }
- void afis()
- {
- for(i=1; i<=n; i++)
- {
- for(j=1; j<=n; j++)
- g<<a[i][j]<<" ";
- g<<'\n';
- }
- }
- int main()
- {
- citire();
- Roy_Warshall();
- afis();
- f.close();
- g.close();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement