MDlab4-5

Matematica Discreta

Ministerul Educaiei a Republicii Moldova

Universitatea Tehnic a Moldovei

Lucrare de laborator la Matematica discretLucrare de laborator nr. 4-5Tema: Drum minim (Alg. Ford si Belman-Kalaba)

A elaborat: st. gr. TI-143

Fiodor Alexandru A verificat: Ceban Cheorghe Chiinu 20151. Scopul lucrrii:

Studierea algoritmilor de determinare a drumurilor minime ntr-un graf.

Elaborarea programelor de determinare a drumului minim ntr-un graf ponderat.

2.Sarcina de baz1. Elaborai procedura introducerii unui graf ponderat;

2. Elaborai procedurile determinrii drumului minim;

3. Realizai un program cu urmtoarele funcii:

introducerea grafului ponderat cu posibiliti de analiz sintactic i semantic;

determinarea drumului minim;

extragerea informaiei la display sau imprimant (valoarea drumului minim i succesiunea vrfurilor care formeaz acest drum).

3.Listingul programului//Lucrare de laborator Nr4.

// Tema:Drum minim (Alg. Ford si Belman-Kalaba).

=#include

#include

#include

typedef struct list

{

int info;

struct list *adr;

}list;

list* pushList(list *prev_el, list *&head_el, int inf);

list** saveList(int n, list **adi_list);

void viewList(int n, list **adi_list);

int** matInitiala(int **mat_ini, int n, int &k, list **adi_list);

void drFord(int v_fin, int **mat_ini, int mat_res[100][100], int k, int val_init, int &lun_dr, int &nr_lin, int n);

void algBK(int **mat_ini, int val_init, int v_start, int mat_res[100][100], int n, int k, int &lun_dr, int &nr_lin);

void afisDrFord(int mat_res[100][100], int nr_lin);

void saveDrFord(int mat_res[100][100], int nr_lin, FILE *fp);

void saveFileList(int n, list **adi_list, FILE *fp);

void afisDrBK(int mat_res[100][100], int nr_lin);

void saveDrBK(int mat_res[100][100], int nr_lin, FILE *fp);

int matDr(int n, int m, int **mat_ini);

void cleanMem(int n, list **adi_list);

int main()

{

list **adi_list;

int n, k, v_pon, v_fin, val_init, lun_dr, nr_lin, v_start, opt, ex_max;

int **mat_ini, mat_res[100][100];

FILE *fp;

printf("Introduceti numarul de virfuri: ");

scanf("%d", &n);

adi_list = saveList(n, adi_list);

mat_ini = matInitiala(mat_ini, n, k, adi_list);

ex_max = matDr(n, k, mat_ini);

system("cls");

do

{

printf("||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||\n");

printf("| Algoritmul Ford si Algoritmul Bellman Kalaba |\n");

printf("||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||\n");

printf("| 1.Afisarea listei de adiacenta |\n");

printf("| 2.Afisarea drumului minim(FORD) |\n");

printf("| 3.Afisarea drumului maxim(FORD) |\n");

printf("| 4.Afisarea drumului minim(Bellman Kalaba) |\n");

printf("| 5.Afisarea drumului maxim(Bellman Kalaba) |\n");

printf("| 0.Iesire |\n");

printf("| |\n");

printf("||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||\n");

printf("Introduceti optiunea dorita: ");

fflush(stdin);

opt = getche();

switch(opt)

{

case '1':

printf("\n");

viewList(n, adi_list);

printf("Pentru a reveni apasa-ti orice tasta...");

fp = fopen("md_saveL4.txt", "w");

fputs("\n", fp);

saveFileList(n, adi_list, fp);

fclose(fp);

getch();

system("cls");

break;

case '2':

printf("\nIntroduce-ti virful pina in care trebuie calculat dr.minim: ");

scanf("%d", &v_fin);

val_init = 2147483600;

drFord(v_fin, mat_ini, mat_res, k, val_init, lun_dr, nr_lin, n);

printf("\nLungimea drumului = %d\n", lun_dr);

printf("\n");

afisDrFord(mat_res, nr_lin);


fp = fopen("md_saveL4.txt", "a");

fprintf(fp, "\nDrumul minim pina in virful %d (Alg.Ford):", v_fin);

fprintf(fp, "\nLungimea drumului = %d\n", lun_dr);

saveDrFord(mat_res, nr_lin, fp);

fclose(fp);

getch();

system("cls");

break;

case '3':

if(ex_max == 0)

{

printf("\nDrum maxim nu exista, pentru ca graful este cu circuite!");


getch();

system("cls");

break;

}

printf("\nIntroduce-ti virful pina in care trebuie calculat dr.maxim: ");

scanf("%d", &v_fin);

val_init = -2147483600;

drFord(v_fin, mat_ini, mat_res, k, val_init, lun_dr, nr_lin, n);


printf("\n");

afisDrFord(mat_res, nr_lin);



fprintf(fp, "\nDrumul maxim pina in virful %d (Alg.Ford):", v_fin);


saveDrFord(mat_res, nr_lin, fp);

fclose(fp);

getch();

system("cls");

break;

case '4':

printf("\nIntroduce-ti virful din care trebuie calculat dr.minim: ");

scanf("%d", &v_start);

val_init = 2147483600;

algBK(mat_ini, val_init, v_start, mat_res, n, k, lun_dr, nr_lin);


printf("\n");

afisDrBK(mat_res, nr_lin);



fprintf(fp, "\nDrumul minim din virful %d (Alg.B-K):", v_fin);


saveDrBK(mat_res, nr_lin, fp);

fclose(fp);

getch();

system("cls");

break;

case '5':

if(ex_max == 0)

{

printf("\nDrum maxim nu exista, pentru ca graful este cu circuite!");


getch();

system("cls");

break;

}

printf("\nIntroduce-ti virful din care trebuie calculat dr.maxim: ");

scanf("%d", &v_start);

val_init = -2147483600;

algBK(mat_ini, val_init, v_start, mat_res, n, k, lun_dr, nr_lin);


printf("\n");

afisDrBK(mat_res, nr_lin);



fprintf(fp, "\nDrumul maxim din virful %d (Alg.B-K):", v_fin);


saveDrBK(mat_res, nr_lin, fp);

fclose(fp);

getch();

system("cls");

break;

default:

system("cls");

}

}while(opt != '0');

return 0;

}

//Functia pentru adaugarea unui element intr-o lista cu parcurgerea de la inceput spre sfirsit

list* pushList(list *prev_el, list *&head_el, int inf)

{

list *tmp = (list *)malloc(sizeof(list));

tmp->info = inf;

tmp->adr = 0;

if(prev_el == 0)

head_el = tmp;

else

prev_el->adr = tmp;

prev_el = tmp;

return prev_el;

}

//Functia pentru introducerea listei de adiacenta

list** saveList(int n, list **adi_list)

{

int i, inf;

list *prev_el, *head_el;

adi_list = (list **)malloc(n * sizeof(list *));

for(i = 0; i < n; i++)

{

prev_el = head_el = 0;

printf("%d |", i + 1);

do

{

scanf("%d", &inf);

prev_el = pushList(prev_el, head_el, inf);

}while(inf != 0);

adi_list[i] = head_el;

}

return adi_list;

}

//Functia pentru afisarea listei de adiacenta

void viewList(int n, list **adi_list)

{

int i;

list *curr_el;

for(i = 0; i < n; i++)

{

curr_el = adi_list[i];

printf("%d |", i + 1);

while(curr_el != 0)

{

printf("%d ", curr_el->info);

curr_el = curr_el->adr;

}

printf("\n");

}

}

//Functia pentru salvarea listei de adiacenta

void saveFileList(int n, list **adi_list, FILE *fp)

{

int i;

list *curr_el;

for(i = 0; i < n; i++)

{


fprintf(fp, "%d |", i + 1);

while(curr_el != 0)

{

fprintf(fp, "%d ", curr_el->info);


}

fprintf(fp, "\n");

}

}

//Functia pentru generarea matricei initiale cu care mai apoi vom lucra

int** matInitiala(int **mat_ini, int n, int &k, list **adi_list)

{

int i, v_pon;

list *curr_el;

k = 0;

mat_ini = (int **)malloc(k * sizeof(int *));

printf("Introduceti ponderile: \n");

for(i = 0; i < n; i++)

{


while(curr_el->info != 0)

{

printf("P[%d, %d] = ", i + 1, curr_el->info);

scanf("%d", &v_pon);

mat_ini = (int **)realloc(mat_ini, (k + 1) * sizeof(int *));

mat_ini[k] = (int *)malloc(4 * sizeof(int));

mat_ini[k][0] = i + 1;

mat_ini[k][1] = curr_el->info;

mat_ini[k][2] = v_pon;


k++;

}

}

return mat_ini;

}

//Functia pentru gasirea drumurilor minime si maxime(Alg.B-K)

void algBK(int **mat_ini, int val_init, int v_start, int mat_res[100][100], int n, int k, int &lun_dr, int &nr_lin)

{

int i, j, ii, con, n_v, min, max, nr_dr, nr_el, nr_ap, pos_v, aux;

int mat_luc[100][n];

for(i = 0; i < n; i++)

{

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

{

if(i == j)

mat_luc[i][j] = 0;

else{

for(ii = 0; ii < k; ii++)

{

con = 0;

if(mat_ini[ii][0] == i + 1 && mat_ini[ii][1] == j + 1)

{

mat_luc[i][j] = mat_ini[ii][2];

con = 1;

break;

}

}

if(con == 0)

mat_luc[i][j] = val_init;

}

}

}

n_v = n;

for(i = 0; i < n; i++)

mat_luc[n_v][i] = mat_luc[i][n - 1];

con = 0;

if(val_init > 0)

{

do

{

n_v++;

for(j = 0; j < n - 1; j++)

{

min = val_init;

for(i = 0; i < n; i++)

if(i != j)

if(mat_luc[j][i] != val_init && mat_luc[n_v - 1][i] != val_init)

if(min > mat_luc[j][i] + mat_luc[n_v - 1][i])

min = mat_luc[j][i] + mat_luc[n_v - 1][i];

mat_luc[n_v][j] = min;

}

mat_luc[n_v][n - 1] = 0;

con = 1;

for(i = 0; i < n; i++)

if(mat_luc[n_v - 1][i] != mat_luc[n_v][i])

{

con = 0;

break;

}

}while(con != 1);

}else{

do

{

n_v++;

for(j = 0; j < n - 1; j++)

{

max = val_init;

for(i = 0; i < n; i++)

if(i != j)

if(mat_luc[j][i] != val_init && mat_luc[n_v - 1][i] != val_init)

if(max < mat_luc[j][i] + mat_luc[n_v - 1][i])

max = mat_luc[j][i] + mat_luc[n_v - 1][i];

mat_luc[n_v][j] = max;

}

mat_luc[n_v][n - 1] = 0;

con = 1;

for(i = 0; i < n; i++)

if(mat_luc[n_v - 1][i] != mat_luc[n_v][i])

{

con = 0;

break;

}

}while(con != 1);

}

lun_dr = mat_luc[n_v][v_start - 1];

nr_dr = 0;

nr_el = 1;

nr_lin = 0;

mat_res[nr_dr][1] = v_start;

do

{

do

{

nr_ap = 0;

pos_v = -1;

for(i = 0; i < n; i++)

if(i != v_start - 1)

if(mat_luc[n_v][v_start - 1] - mat_luc[v_start - 1][i] == mat_luc[n_v][i])

{

nr_ap++;

if(pos_v == -1)

pos_v = i;

}

if(v_start != n)

if(nr_ap > 1)

{

nr_el++;

mat_res[nr_dr][nr_el] = pos_v + 1;

mat_res[nr_dr][0] = nr_el;

do

{

nr_lin++;

for(j = 0; j adr;

free(curr_el);

curr_el = prev_el;

}

}

free(adi_list);

}Concluzie: Efectuind aceasta lucrare , neam familiarizat cu algoritmul aflarii drumului minim.Acest

algoritm ne permite de a afla drumul minim intre orce doua vurfuri prin metoda lui Ford si prin metoda lui Bellman-Kalaba.Acest algoritm se aplic pe larg n practic de exem-

plu laproectarea oselelor sau a diferitor tipuri de comunicaii,deci studiind teoretic acum acest algoritm pe viitotr e posibil s-l aplicm pentru un caz real.

MDlab4-5

Documents

Transcript of MDlab4-5