algoritma warshall

Algoritma Floyd Warshall


Code:

void fwarsh(int nn, double *cmat, double **dist_mat, int **pred_mat)

{

double *dist;

int *pred;

int i,j,k; //loop counters



//inisialisasi struktur data

dist = (double *)malloc(sizeof(double) * nn * nn);

pred = (int *)malloc(sizeof(int) * nn * nn);

memset(dist, 0, sizeof(double)*nn*nn);

memset(pred, 0, sizeof(int)*nn*nn);



//inisialisasi algoritma

for (i=0; i < nn; i++) {

for (j=0; j < nn; j++) {

if (cmat[i*nn+j] != 0.0)

dist[i*nn+j] = cmat[i*nn + j];

else

dist[i*nn+j] = HUGE_VAL;



if (i==j) //diagonal case

dist[i*nn+j] = 0;



if ((dist[i*nn + j] > 0.0) && (dist[i*nn+j] < HUGE_VAL))

pred[i*nn+j] = i;

}

}



//Pengulangan Utama

for (k=0; k < nn; k++) {

for (i=0; i < nn; i++) {

for (j=0; j < nn; j++) {

if (dist[i*nn+j] > (dist[i*nn+k] + dist[k*nn+j])) {

dist[i*nn+j] = dist[i*nn+k] + dist[k*nn+j];

pred[i*nn+j] = pred[k*nn+j];

//printf("updated entry %d,%d with %d\n", i,j, dist[i*nn+j]);

}

}

}

}



/* //Cetak Hasil

for (i=0; i < nn; i++) {

for (j=0; j < nn; j++)

printf("%g ", dist[i*nn+j]);

printf("\n");

} */



if (dist_mat)

*dist_mat = dist;

else

free(dist);



if (pred_mat)

*pred_mat = pred;

else

free(pred);



return;

} //end of fwarsh()









Joined: Mon Mar 31, 2008 6:50 pm

Posts: 840

Re: Algoritma Floyd Warshall



dulugondrong wrote:



Code:

void fwarsh(int nn, double *cmat, double **dist_mat, int **pred_mat)

{

double *dist;

int *pred;

int i,j,k; //loop counters



//inisialisasi struktur data

dist = (double *)malloc(sizeof(double) * nn * nn);

pred = (int *)malloc(sizeof(int) * nn * nn);

memset(dist, 0, sizeof(double)*nn*nn);

memset(pred, 0, sizeof(int)*nn*nn);



//inisialisasi algoritma

for (i=0; i < nn; i++) {

for (j=0; j < nn; j++) {

if (cmat[i*nn+j] != 0.0)

dist[i*nn+j] = cmat[i*nn + j];

else

dist[i*nn+j] = HUGE_VAL;



if (i==j) //diagonal case

dist[i*nn+j] = 0;



if ((dist[i*nn + j] > 0.0) && (dist[i*nn+j] < HUGE_VAL))

pred[i*nn+j] = i;

}

}



//Pengulangan Utama

for (k=0; k < nn; k++) {

for (i=0; i < nn; i++) {

for (j=0; j < nn; j++) {

if (dist[i*nn+j] > (dist[i*nn+k] + dist[k*nn+j])) {

dist[i*nn+j] = dist[i*nn+k] + dist[k*nn+j];

pred[i*nn+j] = pred[k*nn+j];

//printf("updated entry %d,%d with %d\n", i,j, dist[i*nn+j]);

}

}

}

}



/* //Cetak Hasil

for (i=0; i < nn; i++) {

for (j=0; j < nn; j++)

printf("%g ", dist[i*nn+j]);

printf("\n");

} */



if (dist_mat)

*dist_mat = dist;

else

free(dist);



if (pred_mat)

*pred_mat = pred;

else

free(pred);



return;

} //end of fwarsh()