Critticall: Floyd

Floyd algorithm is a way to calculate the cheapest path from every vertex to every vertex, where all direct costs are known. Copy and paste the following source to a file floyd.c and optimize it with Critticall!


$DIMENSION matrix[25]
$DECLAREINT i j k n zero tmp1 tmp2 tmp3 p1 p2 change
$RINVAR n(5,5) matrix[](1,5)
$RETVAR matrix[]

for (i=zero; i<n; i++) {
  for (j=zero; j<n; j++) {
    if (i==j) {
    	tmp1=i*n; tmp1=tmp1+j;
    	matrix[tmp1]=0;
    }	
  }
}    

change=1;

while (change==1) {
  change=0;

  for (i=zero; i<n; i++) {
    for (j=zero; j<n; j++) {
      for (k=zero; k<n; k++) {
    	tmp1=i*n; tmp1=tmp1+j;
    	tmp2=i*n; tmp2=tmp2+k;
    	tmp3=k*n; tmp3=tmp3+j;
    	p2=matrix[tmp2]; p1=matrix[tmp3]; p2=p2+p1;
    	p1=matrix[tmp1];
        if (p1 > p2) {
    	    matrix[tmp1]=p2;
          change=1;
        }
      }
    }
  }

}

We can calculate also just the particular price for the traveling from the vertex number two, to the vertex number three. Here is the code to do just that. A brute force algorithm, what Floyd's is, will be optimized specially for the input and $RETVAR value. A niche optimized algorithm shall be the output. Many niches may be examined with a slight adjusting of the input code.


$DIMENSION matrix[25]
$DECLAREINT i j k n zero tmp1 tmp2 tmp3 p1 p2 change ret_el ret_el_i ret_el_j
$RINVAR n(5,5) matrix[](1,5) ret_el_i(2,2) ret_el_j(3,3)
$RETVAR ret_el

for (i=zero; i<n; i++) {
  for (j=zero; j<n; j++) {
    if (i==j) {
      tmp1=i*n; tmp1=tmp1+j;
      matrix[tmp1]=0;
    } 
  }
}    

change=1;

while (change==1) {
  change=0;

  for (i=zero; i<n; i++) {
    for (j=zero; j<n; j++) {
      for (k=zero; k<n; k++) {
      tmp1=i*n; tmp1=tmp1+j;
      tmp2=i*n; tmp2=tmp2+k;
      tmp3=k*n; tmp3=tmp3+j;
      p2=matrix[tmp2]; p1=matrix[tmp3]; p2=p2+p1;
      p1=matrix[tmp1];
        if (p1 > p2) {
          matrix[tmp1]=p2;
          change=1;
        }
      }
    }
  }

}

tmp1=ret_el_i*n; tmp1=tmp1+ret_el_j;
ret_el=matrix[tmp1];