Advertisement
Five_NT

[C++]Algoritm Roy Warshall

Feb 26th, 2014
281
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.42 KB | None | 0 0
  1. /*
  2.     ******Algoritmul lui Roy Warshall*****
  3.     Algoritmul de determinare a matricei drumurilor.
  4.  
  5. 1. Se citeste matricea de adiacenta a grafului;
  6. 2. Se verifia pentru fiecare nod intermediar (prin conventie nodul k). Daca exista drum intre nodul initial "i" si nodul final "j"; Un nod
  7. "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
  8. 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";
  9.  
  10. Matricea de adiacenta       Matricea drumurilor
  11. 0 1 0 0 0 1             " 1 2 3 4 5 6"
  12. 0 0 1 1 1 0             1 1 1 1 1 1 1
  13. 0 0 0 1 0 1         2 1 1 1 1 1 1
  14. 1 0 0 0 0 1         3 1 1 1 1 1 1
  15. 0 0 0 1 0 1         4 1 1 1 1 1 1
  16. 0 0 0 0 0 0         5 1 1 1 1 1 1
  17.                 6 0 0 0 0 0 0
  18.                "
  19. */
  20.  
  21. #include <fstream>
  22.  
  23. using namespace std;
  24.  
  25. ifstream f("matrice.in");
  26. ofstream g("matrice.out");
  27.  
  28. int a[50][50],n,i,j,k;
  29.  
  30. void citire()
  31. {
  32.     f>>n;
  33.     for(i=1; i<=n; i++)
  34.         for(j=1; j<=n; j++)
  35.             f>>a[i][j];
  36. }
  37. void Roy_Warshall()
  38. {
  39.     for(k=1; k<=n; k++)
  40.         for(i=1; i<=n; i++)
  41.             for(j=1; j<=n; j++)
  42.                 if(a[i][j]==0 && k!=i && k!=j)
  43.                     a[i][j]=a[i][k]*a[j][k];
  44. }
  45. void afis()
  46. {
  47.     for(i=1; i<=n; i++)
  48.     {
  49.         for(j=1; j<=n; j++)
  50.             g<<a[i][j]<<" ";
  51.         g<<'\n';
  52.     }
  53. }
  54. int main()
  55. {
  56.     citire();
  57.     Roy_Warshall();
  58.     afis();
  59.     f.close();
  60.     g.close();
  61.     return 0;
  62. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement