Ministerul Educaţiei a Republicii Moldova

Universitatea Tehnică a Moldovei

Lucrare de laborator la Matematica discretă

Lucrare de laborator nr. 4

Tema: ” Algoritmi de aflare a drumului minim. ”

A elaborat: st. gr. AI-101 A verificat: conf.univ.

Chişinău 2012

1. Scopul lucrării:

Studierea algoritmilor de determinare a drumurilor minime într-un graf. Elaborarea programelor de determinare a drumului minim într-un graf ponderat.

2.Sarcina de bază1. Elaboraţi procedura introducerii unui graf ponderat;2. Elaboraţi procedurile determinării drumului minim;3. Realizaţi un program cu următoarele funcţii:

introducerea grafului ponderat cu posibilităţi de analiză sintactică şi semantică; determinarea drumului minim; extragerea informaţiei la display sau imprimantă (valoarea drumului minim şi succesiunea vârfurilor care formează

acest drum). 3.Listingul programului

//Lucrare de laborator Nr4. // Tema:Drum minim (Alg. Ford si Belman-Kalaba).#include <stdio.h>#include <conio.h>#include <alloc.h>#define MAX 30000//===================================================================

/* Declararea structurilor si variabilelor globale */struct List{

int v;int w;struct List *next;

};struct Graph{

int h;int p;struct List *first;struct List *last;

}*G;int N,V;//-------------------------------------------------------------------

/* Initializarea functiilor */void F();void BK();void Menu();void Prezt();void ListAd();void ElebList();void DrumFord(int);//-------------------------------------------------------------------

/* Corpul principal */void main(){ Prezt(); Menu();}//-------------------------------------------------------------------

/* Algoritmul drum minim Ford */void F(){ int i,f=1;

struct List *c; _setcursortype(_NORMALCURSOR); if(G==NULL) return; for(i=0;i<N;i++) { G[i].p=-1;

G[i].h=MAX; } printf("\n\t"); textcolor(6); cprintf("Dati virful initial: "); scanf("%d",&V); _setcursortype(_NOCURSOR); G[--V].h=0; while(f) { f=0;

for(i=0;i<N;i++) { c=G[i].first;

while(c!=G[i].last){ if(G[c->v].h>G[i].h+c->w) { G[c->v].h=G[i].h+c->w;

G[c->v].p=i; f=1;

} c=c->next;}

} } for(i=0;i<N;i++) { textcolor(3); cprintf("\n\r Drum min din %d in %d este",V+1,i+1);

if(G[i].h==MAX) {textcolor(4); cprintf(" nu exista.");} else { DrumFord(i);

textcolor(2); cprintf(" : Are lungimea %d.\r",G[i].h); textcolor(15);

} }}//-------------------------------------------------------------------

/* Algoritmul drum minim Belman-Kalaba */void BK(){ int *t,i,j,k,f=1; struct List *c; int *P=(int *)malloc(N*sizeof(int )); int *VK=(int *)malloc(N*sizeof(int )); int **M=(int **)malloc(N*sizeof(int *)); int *VK_1=(int *)malloc(N*sizeof(int )); _setcursortype(_NORMALCURSOR); for(i=0;i<N;i++) M[i]=(int *)malloc(N*sizeof(int)); for(i=0;i<N;i++)

for(j=0;j<N;j++) M[i][j]=(i==j)?0:MAX; for(i=0;i<N;i++) { c=G[i].first;

while(c!=G[i].last)

{ M[i][c->v]=c->w;c=c->next;

} } printf("\n\t"); textcolor(6); cprintf("Dati virful final: "); scanf("%d",&V); _setcursortype(_NOCURSOR); V--; for(i=0;i<N;i++) { VK_1[i]=M[i][V];

P[i]=-1; } while(f) { for(i=0;i<N;i++) VK[i]=MAX;

for(i=0;i<N;i++) for(j=0;j<N;j++)

if(i!=j && VK[i]>VK_1[j]+M[i][j]){ VK[i]=VK_1[j]+M[i][j]; P[i]=j;}

VK[V]=0; for(i=0;i<N && VK[i]==VK_1[i];i++); f=(i==N)?0:1; t=VK_1; VK_1=VK; VK=t;

} for(i=0;i<N;i++) { textcolor(3); cprintf("\n Drumul min din %d in %d este",i+1,V+1);

if(VK_1[i]==MAX) {textcolor(4); cprintf(" nu exista.");} else { for(k=i,j=0;j<N && P[k]!=-1 && k!=V;j++)

{ if(!j) printf(": %d",k+1); else printf("->%d",k+1);k=P[k];

} if(k==V || i<N-1) printf("->A%d",V+1); else printf(":A %d",V+1); textcolor(2); cprintf(" : Are lungimea: %d.\r",VK_1[i]); textcolor(15);

} } for(i=0;i<N;i++) free(M[i]); free(P); free(M); free(VK); free(VK_1);}//-------------------------------------------------------------------

/* Meniul principal */void Menu(){ int m; textcolor(15); cprintf("\nBLIN!"); clrscr(); _setcursortype(_NOCURSOR); printf("\n\

ЙННННННННННННННННННННННННННННННННННННННННН»\n\

є [ MENIU ] є\n\МННННННННННННННННННННННННННННННННННННННННН%c\n\є [1] - Introducerea grafului: ( LstAd ).є\n\є є\n\є [2] - Drum minim: (Alg. Ford ).є\n\є є\n\є [3] - Drum minim: (Alg.Belman-Kalaba).є\n\є є\n\є Esc - Iesirea. є\n\ИНННННННННННННННННННННННННННННННННННННННННј\n",185);

do m=getch();while((m<49 || m>51) && m!=27);

clrscr(); switch(m) {

case 49: ListAd(); break;case 50: F(); getch(); break;case 51: BK(); getch(); break;case 27: ElebList(); return;

} Menu();}//-------------------------------------------------------------------

/* Prezentarea temei */void Prezt(){ clrscr(); _setcursortype(_NOCURSOR); printf("\n\n\n\n\t\t"); textcolor(3); cprintf("Lucrare de laborator Nr4 la Matematica Discreta."); printf("\r\n\n\t\t\t\t"); cprintf("Drum minim."); textcolor(15); getch();}//-------------------------------------------------------------------

/* Lista de adiacenta si matricea ponderilor*/void ListAd(){ int i,v,w; struct List *c;//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

/* LstAd */ _setcursortype(_NORMALCURSOR); if(G) ElebList(); printf("\n\t"); textcolor(3); cprintf("Dati nr de virfuri a grafului : "); scanf("%d",&N); G=(struct Graph *)malloc(N*sizeof(struct Graph)); printf("\n\t"); textcolor(14); cprintf("Introduceti lista de adiacenta: \n\n\r"); for(i=0;i<N;i++) { textcolor(3); cprintf("%d|",i+1);

textcolor(15); G[i].first=(struct List*)malloc(sizeof(struct List));

G[i].last=G[i].first; G[i].last->next=NULL; G[i].last->v=-1; scanf("%d",&v);; if(N<v || v<0) { clrscr();

printf("\n\n\n\n\n\t\t\t");_setcursortype(_NOCURSOR);textcolor(4); cprintf("Eroare!");textcolor(15);getch();Menu();

} while(v) { G[i].last->v=v-1;

G[i].last->next=(struct List*)malloc(sizeof(struct List));G[i].last=G[i].last->next;G[i].last->next=NULL;G[i].last->v=-1;scanf("%d",&v);if(N<v || v<0){ clrscr(); printf("\n\n\n\n\n\t\t\t"); _setcursortype(_NOCURSOR); textcolor(4); cprintf("Eroare!"); textcolor(15); getch(); Menu();}

} }//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

/* MatPnd */ clrscr(); printf("\n\t"); textcolor(6); cprintf("Introduceti ponderea pentru fiecare arc:\n\n\r"); for(i=0;i<N;i++) { G[i].last=G[i].first;

while(G[i].last->v+1) { textcolor(3); cprintf(" u%d%d| ",i+1,G[i].last->v+1);

textcolor(15);scanf("%d",&w);G[i].last->w=w;G[i].last=G[i].last->next;

} }//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++}//-------------------------------------------------------------------

/* Eleberarea listei */void ElebList(){ struct List *c,*t;

while(N--) { c=G[N].first;

while(c!=G[N].last) { t=c->next;

free(c);c=t;

} } free(G);}//-------------------------------------------------------------------

/* Vizualizarea drumului minim Ford */void DrumFord(int v){ int k; if(v!=V) {k=v; DrumFord(G[v].p);} if(k!=v) printf(": %d",v+1);

else {printf("->%d",v+1); k++;}}//===================================================================

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 comunicaţii,deci studiind teoretic acum acest algoritm pe viitotr e posibil să-l aplicăm pentru un caz real.