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];
|