Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

Floyd's Algorithm

By: a guest on Apr 18th, 2012  |  syntax: C++  |  size: 1.63 KB  |  views: 48  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string>
  4. using namespace std;
  5.  
  6.  
  7. int matrixFloyd(int *C, int n, int *A, string* s)
  8. {
  9.  
  10.   int i,j,k;
  11.  
  12.  
  13.   for (i=0; i<n; i++)
  14.   {
  15.     for (j=0; j<n; j++)
  16.     {
  17.       if ( *(C+i*n+j) == -1)
  18.       {
  19.         *(A+i*n+j) = 999999999;
  20.       }
  21.       else
  22.       {
  23.         *(A+i*n+j) = 1;
  24.         char sz[3]="";
  25.         sprintf(sz,"%d",j+1);
  26.         s[i*n+j]=sz;
  27.       }
  28.     }
  29.   }
  30.  
  31.  
  32.   for (i=0; i<n; i++)
  33.   {
  34.     *(A+i*n+i) = 0;
  35.   }
  36.  
  37.  
  38.   for (k=0; k<n; k++)
  39.   {
  40.     for (i=0; i<n; i++)
  41.     {
  42.       for (j=0; j<n; j++)
  43.       {
  44.         if ( *(A+i*n+k) + *(A+k*n+j) < *(A+i*n+j) )
  45.        
  46.           // A[i][j] = A[i][k] + A[k][j];
  47.           *(A+i*n+j) = *(A+i*n+k)+ *(A+k*n+j);
  48.       }
  49.     }
  50.   }
  51.  
  52.   return 0;
  53. }    
  54.  
  55. void testFunction()
  56. {
  57.  
  58.  
  59.    int x, y;
  60.   int n=5;
  61.   int *C=new int[n*n];
  62.  
  63. C[0 ]=0;C[1 ]=2;C[2 ]=-1;C[3 ]=1;C[4 ]=8;
  64. C[5 ]=6;C[6 ]=0;C[7 ]=3;C[8 ]=2;C[9 ]=-1;
  65. C[10 ]=-1;C[11 ]=-1;C[12 ]=0;C[13 ]=4;C[14 ]=-1;
  66. C[15 ]=-1;C[16 ]=-1;C[17 ]=2;C[18 ]=0;C[19 ]=3;
  67. C[20 ]=3;C[21 ]=-1;C[22 ]=-1;C[23 ]=-1;C[24 ]=0;
  68.  
  69.  
  70.   int* A = new int[n*n];
  71.   string* s = new string[n*n];
  72.   printf("Beginning matrix:\n");
  73.   for(x=0;x<n;x++)
  74.   {
  75.     for(int y=0;y<n;y++)
  76.     {
  77.       printf("%d ",*(C+x*n+y));
  78.     }
  79.     printf("\n");
  80.   }
  81.  
  82.  
  83.   matrixFloyd(C,n,A,s);
  84.  
  85.   printf("Shortest distances:\n");
  86.   for(x=0;x<n;x++)
  87.   {
  88.     for(y=0;y<n;y++)
  89.     {
  90.       printf("%d ",*(A+x*n+y));
  91.     }
  92.     printf("\n");
  93.   }
  94.  
  95.     delete [] A;
  96.     delete [] C;
  97.     delete [] s;
  98.  
  99. }
  100.  
  101. int main()
  102. {
  103.   testFunction();
  104.   char c;
  105.   scanf("%c",&c);
  106. }