Scrieti programul C care determina cel mai scurt drum dintre nodurile s si t folosind algoritmul lui 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 imposibilitatea 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 vom memora costurile minime ale drumurilor la nodurile grafului care au ca nod inital nodul s : distanta[i] = cost minim al drumului de la s 838i85i 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 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 algoritm 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.
Programul C:
#include <stdio.h>
#include <conio.h>
#include <ctype.h>
#include <graphics.h>
#include <stdlib.h>
#include <math.h>
#define PI (2*asin(1))
#define r 100
#define NrNoduri 6
#define FALSE 0
#define TRUE 1
#define Membru 1
#define Nemembru 0
#define INFINIT 100
#define CALE 'c:borlandcbgi'
typedef int TipCheie;
typedef TipCheie TipEl;
typedef struct
TipArc;
typedef TipEl TipTabEl[NrNoduri];
typedef TipArc TipMatAdi[NrNoduri][NrNoduri];
typedef int vector[NrNoduri];
typedef int mat[NrNoduri][NrNoduri];
typedef struct
Graf;
Graf g;
TipTabEl precede;
int s, t;
void InitGraf(Graf *g)
}/* InitGraf */
void Creare(Graf *g)
printf('Nodul de sosire: ');
fflush(stdin);
while(scanf('%d', &j)!=1 || j<0)
printf('Valoare arc: ');
fflush(stdin); scanf('%d', &v);
g->Arce[i-1][j-1].adi = TRUE;
g->Arce[i-1][j-1].val = v;
printf('Mai introduceti?(D/N)');
fflush(stdin);
scanf('%c', &ch); ch = toupper(ch);
}
}/* Creare */
int DrumScurt(TipTabEl precede, mat valoare, int s, int t)
distanta[s] = 0;
perm[s] = Membru;
curent = s;
k = s;
while((curent != t) && (contor<NrNoduri))
if(distanta[i]<distMica)
}
curent = k;
perm[curent] = Membru;
contor++;
}/* end while */
return distanta[t];
}/* DrumScurt */
void initializare_mod_grafic(void)
} /* initializare */
void afisareNoduri(Graf g)
;
int i, xi, yi, x0, y0;
x0 = getmaxx()/2;
y0 = getmaxy()/2;
for(i=0; i<NrNoduri; i++)
setcolor(WHITE);
}/* afisareNoduri */
void afisareGraf(Graf g)
outtextxy(getmaxx()-430, getmaxy()-10, 'Apasati o tasta pentru a termina!');
getch();
closegraph();
}/* afisareGraf */
void main(void)
printf('Introduceti urmatorul nod: ');
while(scanf('%d', &t)!=1 || t<=0)
for(i=0; i<NrNoduri; i++)
for(j=0; j<NrNoduri; j++)
if(g.Arce[i][j].val!=-1)
valoare[i][j] = g.Arce[i][j].val;
else valoare[i][j] = INFINIT;
drum = DrumScurt(precede, valoare, s-1, t-1);
printf('Drumul de la %d la %d are valoarea minima: %dn',s, t, drum);
printf('Apasati o tasta pentru a continua!n');
getche();
break;
case 'E':break;
default:printf('Optiune gresita!n');
}
}while(c != 'E');
}/* main */
|
