Scrieti programul C care determina cel mai scurt drum intre nodurile s si t intr-un graf orientat valoric si permite vizualizarea celui mai scurt drum (in sens invers cu vizualizare a grafului) (Dijkstra) .
Descrierea algoritmului:
Intru-un graf valoric , prin cel mai scurt drum de la s la t vom intelege un drum de la s la t in care suma valorilor arcelor apartinand drumului este minima.
Sa consideram o matrice valorica valoare , cu proprietatea ca valoare[i,j] este valoare , costul arcului <i,j>, daca exista un astfel de arc, sau o valoare forte mare, ceva care ne spune imposibilitate existentei unui arc de lai la j . Vom numi infinit variabila care contine cel mai mare intreg posibil asociat unui arc.
Intr-un tablou numit distanta 454j95e vom memora costurile minime ale drumurilor la noduri grafului care au ca nod inital nodul s : distanta[i] = cost minim al drumului de la s la i .
Initial, acest tablou va contine distanta[s]=0
distanta[i]=infinit, i ≠ s
Aceasta distanta se va recalcula la fiecare pas al algoritmului. Distanta cea mai scurta de la s la orice nod al grafului va fi data initial de arcul de cost minim de la s la nodurile grafului. Urmatorul drum in ordinea cresterii costurilor ( cu origine in s ) va fi un alt arc care trece prin i si apoi ajunge in j.
Vom nota variabila care contine toate nodurile pentru care distanta de la s la i este determinata perm, cu proprietatea ca perm[i] va indica nodul a carui distanta minima de la s la i este deja determinata.
Initial , sigurul nod din tablou este s. Vom adauga pe rand nodurile in tablou, in ordinea cresterii distantelor.
Exemplu:
perm =
perm =
perm =
perm =
perm =
La fiecare pas, adaugam in perm acel nod k I N perm, cu proprietatea ca drumul minim de la s la k are cel mai mic cost, dintre toate drumurile de la s la p, cu
p I N perm . Algoritmul va mentine o variabila curent, care este nodul care a fost adaugat in perm cel mai recent. Initial curent=1. De fiecare data cand un nod nod este adaugat in perm, distanta trebuie recalculata pentru toti succesorii nodului curent.
Daca distanta[curent] + valoare[curent,i] < distanta[i], atunci
distanta[i] = valoare[curent,i] + distanta[curent]
Dupa ce distanta a fost calculata pentru fiecare succesor al lui curent, distanta[j] va contine cel mai scurt drum. Atunci nodul k ce nu apartine lui perm pentru care distanta[k] este cea mai mica dintre toate distantele de la s la t, acest nod k va fi adaugat in perm. Curent va fi modificat la valoarea k si procedeul se repeta. Cand t devine un membru al lui perm, distanta[t] este cea mai mica distanta de la s la t algoritmul se termina.
Rutina Pascal ce implementeaza acest algorimt va contine si un tablou precede, precede[i] contine nodul precedent lui i. Tabloul perm va fi folosit doar pentru a mentine urma drumurilor ce apartin celui mai scurt drum.
Rezolvare:
Scrieti programul C care determina cel mai scurt drum intre nodurile s si t intr-un graf orientat valoric si permite vizualizarea celui mai scurt drum (in sens invers cu vizualizare a grafului) (Dijkstra) .
#include<stdio.h>
#include<conio.h>
#include<ctype.h>
#include<math.h>
#include<graphics.h>
#define R 200
#define pi M_PI
#define r 15
#define maxN 20
#define INFINIT 100
#define Membru 1
#define Nemembru 0
typedef char TipCheie;
typedef TipCheie TipEl;
typedef int TipContor;
typedef TipEl TipTabEl[maxN];
typedef int TipVal;
typedef struct
TipAdi;
typedef TipAdi TipMatAdi[maxN][maxN];
typedef struct
Graf;
typedef struct
TipArc;
typedef int mat[maxN][maxN];
typedef int vector[maxN];
Graf g;
TipEl e,c1,c2;
int IndiceNod;
TipArc IndiceArc;
TipVal val;
mat Valoare;
vector Precede;
int lung=INFINIT;
char s,t;
char c,S[2]=;
int i,j,k,is,it;
double xk,yk,x0,y0,x1,y1,x2,y2,x3,y3,x,y,xi,yi,xj,yj;
double ALFA,ALFA1,ALFA2;
void Init_Mod_Grafic(void)
}//initmodgrafic
void Desenare_Noduri(void)
}//Desenare_Noduri
void Desenare_Graf(void)
}//Desenare_Graf
void Afisare_Matrice(void)
printf('nMatricea valorica esten');
for(i=0;i<=g.Contor-1;i++)
printf('n');
}//Afisare_Matrice
void Inser_Nod(Graf *g,TipEl e)
}//Inser_Nod
int Cauta_Nod(Graf g,TipCheie cheia)
//Cauta_Nod
void Inser_Arc(Graf *g,TipArc IndiceArc,TipVal val)
//Inser_Arc
void Suprima_Nod(Graf *g,int IndiceNod)
g->Contor--;
}//Suprima_Nod
void Suprima_Arc(Graf *g,TipArc IndiceArc)
//Suprima_Arc
void creare(void)
//introducem multimea arcelor
if(g.Contor==0)
printf('Nu avem noduri!n');
else
}
printf('Mai adaugi?(D/N):');
fflush(stdin);scanf('%c',&c);c=toupper(c);
}
}
}//creare
int Drum_Scurt(mat Valoare,int is,int it,vector Precede)
Distanta[is]=0;
Perm[is]=Membru;
curent=is;
k=is;
contor=0;
while((curent!=it)&&(contor<2*g.Contor))
if(Distanta[i]<DistMica)
}
curent=k;
Perm[curent]=Membru;
contor++;
}
return Distanta[it];
}//Scurt_Drum
void main(void)
}
break;
case 'S':printf('Nodul sursa:');
fflush(stdin);scanf('%c',&c1);c1=toupper(c1);
IndiceArc.lin=Cauta_Nod(g,c1);
if(IndiceArc.lin==-1)
printf('Nod eronat!n');
else
break;
case 'M':printf('nMatricea de adiacenta esten');
Afisare_Matrice();
break;
case 'L':printf('Introdu nodul sursa:');
fflush(stdin);scanf('%c',&s);
s=toupper(s);
is=Cauta_Nod(g,s);
if(is==-1)
printf('Nod sursa eronat!n');
else
printf('Tastati enter!n');getch();
}
}
}
break;
case 'E':break;
default:printf('Ati tastat optiune eronata!n');
break;
}//switch
Desenare_Graf();
printf('Tastati enter!n');getch();
}while(op!='E');
closegraph();
}//main
|
