CUPRINS

1. Găsirea drumurilor într-un graf orientat2. Drumuri optime într-un graf orientat3. Algoritmul lui Dijkstra4. Algoritmul lui Dantzig5. Algoritmul Bellman-Ford6. Determinarea drumurilor minime în grafuri

orientate aciclice7. Algoritmul Floyd-Warhall pentru drumuri

minime8. Algoritmul Floyd-Warshall pentru drumuri

maxime9. Algoritmul Bellman-Kalaba10. Drumuri minime într-un labirint

1

11. Găsirea drumurilor într-un graf orientat

Dacă privim graful ca imagine a unui sistem, nodurile reprezentând componentele sistemului, atunci o interpretare imediată a unui arc (xi,xj) este că, componenta xi influenţează direct componenta xj. Dacă nodurile au semnificaţia de stări posibile ale unui sistem atunci un arc (xi,xj) semnifică faptul că sistemul poate trece direct din starea xi în starea xj. În ambele cazuri se vede că avem de-a face doar cu informaţii despre legături directe; totuşi, chiar dacă o componentă xi nu influenţează direct componenta xj ea o poate influenţa prin intermediul altor componente, existând un şir de componente intermediare: x1 x2 ,..., xk, fiecare influenţând-o direct pe următoarea şi xi

direct pe x1 iar xk direct pe xj. Astfel, dacă dintr-o stare xi nu se poate trece direct într-o stare xj s-ar putea totuşi în mai multe etape, prin alte stări intermediare. Deoarece găsirea acestor influenţe sau treceri posibile este de obicei foarte importantă iar pentru un sistem cu mii sau zeci de mii de componente acest lucru nu mai poate fi făcut "din ochi", este necesară formalizarea noţiunii de "influenţe" şi "treceri" posibile, nu neapărat directe. Acest lucru a şi fost făcut mai sus, deoarece este evident că "xi influenţează xj" sau "din starea xi se poate trece în starea xj" este echivalent cu existenţa în graf a unui drum de la nodul xi la nodul xj.

În continuare vom da un algoritm prin care putem găsi toate drumurile dintr-un graf orientat cu un număr finit de noduri.

Pasul 1. Se construieşte matricea booleană a adiacenţelor directe corespunzătoare grafului, notată cu A. În aceasta se află, evident, toate drumurile de lungime 1.

Este interesant de văzut ce legătură există între această matrice şi drumurile de lungime 2. Fie două noduri xi şi xj oarecare din graf. Existenţa unui drum de lungime 2 între ele presupune existenţa unui nod xk, din graf, cu proprietatea că există atât arcul (xi,xk) cât şi arcul (xi,xk). Pentru a vedea dacă acesta există, luăm pe rând fiecare nod al grafului şi verificăm dacă există sau nu ambele arce ((xi,xk) şi (xi,xk)). Aceasta este echivalent cu a verifica dacă, în matricea booleană a adiacenţelor directe, există vreun indice k astfel încât elementul k al liniei i şi elementul k al coloanei j să fie ambele egale cu 1. Dacă folosim operaţiile algebrei booleene de adunare şi înmulţire:

0 1 0 10 0 1 0 0 01 1 1 1 0 1

atunci verificările de mai sus sunt echivalente cu a verifica dacă elementul de pe poziţia (i,j) din A2

este egal cu 1. Valoarea 1 spune doar că există cel puţin un drum de lungime 2 de la xi la xj. Dacă dorim să vedem şi câte sunt, vom folosi regulile de înmulţire şi adunare obişnuită.

De asemenea, se poate observa că existenţa unui drum de lungime 3 de la xi la xj presupune existenţa unui nod xk astfel încât să existe un drum de lungime 2 de la xi la xk şi un arc de la xk la xj, care este echivalent cu a verifica dacă există vreun indice k astfel încât elementul k al liniei i din matricea A2 şi elementul k al coloanei j din A sunt ambele egale cu 1 sau, mai simplu, dacă elementul (i,j) din A3 este 1.

Din cele de mai sus se observă că existenţa drumurilor de lungime k este dată de valorile matricei Ak, dacă s-au folosit regulile algebrei booleene şi numărul lor este dat de Ak, dacă s-au folosit regulile obişnuite.

Pasul 2. Vom calcula succesiv puterile lui A până la puterea An-1

Dacă între nodurile xi şi xj există un drum de lungime ³ n atunci el va conţine un număr de noduri mai mare sau egal cu n+1 şi, cum în graf sunt doar n vârfuri, este clar că cel puţin unul, să zicem xk, va apărea de două ori. Vom avea în acest caz un drum de la xi până la prima apariţie a lui xk, şi un drum de la ultima apariţie a lui xk la xj. Eliminând toate nodurile dintre prima apariţie a lui xk

şi ultima apariţie a sa vom obţine un drum de la xi la xj, în care xk apare o singură dată. Aplicând

2

acest procedeu pentru toate nodurile care apar de mai multe ori pe drum, vom obţine un drum de la xi la xj, în care fiecare nod apare o singură dată (deci un drum elementar), care are evident cel mult n-1 arce. În concluzie, dacă există vreun drum de la xi la xj atunci există şi un drum elementar şi, deci, va exista o putere a lui A, între A1 şi An-1, în care poziţia (i,j) este diferită de 0. Pentru deciderea existenţei unui drum între oricare două noduri este suficientă, deci, calcularea doar a primelor n-1 puteri ale lui A. Se calculează matricea D = A + A2 + ... + An-1

Dacă ne interesează doar existenţa drumurilor dintre noduri, nu şi numărul lor, vom folosi înmulţirea şi adunarea booleană şi conform observaţiei de mai sus:

1, daca exista drum de la xi la xj

dij = 0, in caz contrar

Procedeul de mai sus nu asigură decât aflarea faptului dacă există sau nu drum între două noduri, eventual ce lungime are şi câte sunt de această lungime. Totuşi, în problemele practice cel mai important este să ştim care sunt efectiv aceste drumuri.

Deoarece toate drumurile pot fi descompuse în drumuri elementare şi în problemele practice în general acestea sunt cele care interesează, paşii următori ai algoritmului vor fi dedicaţi găsirii lor.

Pentru găsirea acestora se foloseşte reprezentarea grafului prin matricea latină. Matricea latină este o matrice pătratică nxn în care pe o poziţie aij va fi xixj dacă există arcul (xi,xj) şi 0 în caz contrar.

Pasul 3. Construim matricea latină L asociată grafului, unde:

xixj, dacă există arcul (xi,xj)lij =

0, în caz contrar şi matricea L(1), definită prin:

xj, dacă există arcul (xi,xj)l(1)

ij = 0, în caz contrar

numită matricea latină redusă.

Găsirea unui drum de lungime 2 de la xi la xj presupune găsirea unui nod cu proprietatea că există arcele (xi,xk) şi (xk,xj) şi memorarea vectorului (xi, xk, xj). Aceasta este echivalent cu a găsi un indice k astfel încât elementul de pe poziţia k a liniei i, din matricea L, să fie xi,xk şi elementul de pe poziţia k al coloanei j, din matricea L(1), să fie xj. Vom înmulţi deci matricea L cu matricea L(1), folosind însă nişte reguli de calcul speciale, numite înmulţire şi adunare latină.

Definiţia 1: Se numeşte alfabet o mulţime de semne numite simboluri sau litere {si│iÎI} unde I este o mulţime oarecare de indici, finită sau nu.Definiţia 2: Se numeşte cuvânt un şir finit de simboluri notat si1si2.....sin.Definiţia 3: Se numeşte înmulţire latină o operaţie definită pe mulţimea cuvintelor unui alfabet, notată "xL", astfel:

si1si2.....sin xL sj1sj2.....sjm = si1si2.....sin sj1sj2.....sjm

(produsul a două cuvinte se obţine prin concatenarea lor)Înmulţirea latină este asociativă, are ca element neutru cuvântul vid, nu e comutativă şi un element este inversabil doar dacă este cuvântul vid.Definiţia 3: Se numeşte adunare latină o funcţie definită pe mulţimea cuvintelor unui alfabet cu valori în mulţimea parţilor mulţimi cuvintelor, notată „+Lastfel:

3

si1si2.....sin „+L sj1sj2.....sjm = (si1si2.....sin, sj1sj2.....sjm)(suma a două cuvinte este mulţimea formată din cele două cuvinte)

Pasul 4. Se calculează succesiv matricile:

L2 = L xLL(1), L3 = L2xLL(1), ...,Lk+1 = LkxLL(1)

folosind operaţiile de înmulţire şi adunare latină, alfabetul fiind mulţimea nodurilor grafului, unde operaţia de înmulţire este uşor modificată, produsul dintre două elemente ale matricilor fiind 0, dacă unul dintre ele este 0 sau au un nod comun şi este produsul latin al lor, în caz contrar.

Din felul cum a fost construită, matricea Lk va conţine toate drumurile elementare de lungime k. Cum un drum elementar poate avea cel mult n noduri (câte are graful cu totul) rezultă că:

primele n-1 puteri ale lui L conţin toate drumurile elementare din graf; puterile lui L mai mari sau egale cu n au toate elementele egale cu 0; matricea Ln-1 conţine toate drumurile hamiltoniene din graf (dacă există).

Observaţie: Deoarece obţinerea matricii D prin metoda de mai sus presupune un volum foarte mare de calcule (de exemplu, dacă graful are 100 de noduri, ridicarea unei matrici de 100×100 la puterea 100) pentru obţinerea acesteia se poate aplica şi următorul algoritm:

Pas 1. Se construieşte matricea de adiacenţă A;Pas 2. Pentru fiecare linie i se adună boolean la aceasta toate liniile j pentru care aij=1.Pas 3. Se reia pasul 2 până când, după o aplicare a acestuia, matricea rămâne aceeaşi (nu

mai apare nici un 1)Ultima matrice obţinută este matricea drumurilor D numită şi matricea conexiunilor totale.Această metodă, deşi mai simplă nu spune însă şi care sunt aceste drumuri, pentru găsirea lor

aplicându-se, de exemplu, înmulţirea latină.

Drumuri optime într-un graf orientat În marea majoritate a problemelor care pot fi modelate prin grafuri nu ne interesează numai

dacă există sau nu legături între componentele reprezentate prin nodurile grafului ci şi intensitatea acestora. Această intensitate are semnificaţia unei valori numerice (pozitive sau negative) asociate arcului corespunzător legăturii a cărei intensitate o măsoară.

În aplicaţiile economice această valoare poate fi: lungimea drumului dintre două localităţi; costul parcurgerii rutei reprezentate prin arcul corespunzător; durata parcurgerii rutei respective; cantitatea transportată pe ruta respectivă; capacitatea maximă a rutei respective; câştigul realizat prin trecerea de la o stare la alta a sistemului; consum de energie pentru efectuarea trecerii respective; punctaj realizat etc.

Una din problemele care poate apărea în aceste situaţii este găsirea, pentru o anumită pereche de noduri (sau mai multe perechi), a drumului optim între acestea.

Pentru formalizarea problemei vom introduce noţiunea de valoare a unui drum, care este egală cu suma valorilor arcelor care îl compun. Vom nota în continuare valoarea unui arc (xi,xj) cu c(xi,xj) sau cu cij. În aceste condiţii putem enunţa problema drumului optim astfel:

4

"Dat un graf G=(X,U) şi o funcţie care asociază fiecărui arc o valoare reală, să se găsească, pentru o pereche dată de noduri, drumul (drumurile) de valoare optimă (minimă sau/şi maximă) între cele două noduri şi valoarea acestuia (acestora)"

Deoarece este vorba de găsirea minimului unei mulţimi de numere reale, prima întrebare care se pune este dacă aceasta admite minim. Dacă mulţimea nodurilor grafului este infinită atunci pot exista o infinitate de drumuri elementare distincte între cele două noduri şi mulţimea valorilor acestora poate avea orice formă (închisă sau nu, mărginită sau nu) devenind foarte greu de caracterizat cazurile când minimul dorit există. Deoarece totuşi majoritatea covârşitoare a problemelor economice se modelează prin grafuri cu număr finit de noduri, ne vom limita în continuare doar la acestea.

Un număr finit de noduri n atrage după sine existenţa unui număr finit de arce (cel mult n2) şi a

unui număr finit de drumuri elementare ( cel mult n×n!×

1-n

1k k!1

). Deoarece oricărui drum d îi corespunde un drum elementar de (obţinut prin eliminarea tuturor subcircuitelor lui d) putem calcula valoarea oricărui drum ca sumă între valoarea drumului elementar corespunzător şi valorile unor subcircuite ale sale, fiecare înmulţită cu numărul de parcurgeri ale circuitului respectiv.

În concluzie, dacă există un circuit de valoare negativă înseamnă că există drumuri de valoare oricât de mică (cele care conţin acest circuit), obţinută prin parcurgerea acestuia de oricâte ori dorim) şi, deci, mulţimea valorilor drumurilor este nemărginită inferior, neexistând drum de valoare minimă. Dacă există un circuit de valoare pozitivă atunci există drumuri de valoare oricât de mare şi mulţimea valorilor drumurilor este nemărginită superior, neexistând drum de valoare maximă.

Dacă nu există circuite de valoare negativă atunci valoarea oricărui drum este mai mare sau egală cu a drumului elementar corespunzător, deci drumul de valoare minimă (dacă există) va fi un drum elementar. Cum mulţimea drumurilor elementare este finită (şi deci şi mulţimea valorilor lor) va avea minorant şi am lămurit problema compatibilităţii problemei. Analog, dacă nu există circuite de valoare pozitivă atunci valoarea oricărui drum este mai mică sau egală cu a drumului elementar corespunzător, deci drumul de valoare maximă (dacă există) va fi un drum elementar. Cum mulţimea drumurilor elementare este finită (şi deci şi mulţimea valorilor lor), va avea majorant.

Obs. 1. Dacă în graf nu există decât arce de valoare pozitivă atunci există drum de valoare minimă.

Obs. 1. Dacă în graf nu există decât arce de valoare negativă atunci există drum de valoare maximă.

Obs. 1. Dacă în graf nu există circuite atunci există şi drum de valoare minimă şi drum de valoare maximă.

Deoarece din cele de mai sus se sesizează importanţa existenţei circuitelor într-un graf vom da în continuare un algoritm de depistare a existenţei circuitelor într-un graf:

Pasul 1. Se construieşte mulţimea A formată din nodurile pentru care toate arcele incidente sunt incidente spre interior ( noduri în care toate arcele "intră" sau, altfel spus, noduri din care nu "pleacă" nici un arc).

Pasul 2. Se găsesc toate nodurile care nu sunt din A pentru care toate arcele incidente au cealaltă extremitate în A (noduri din care se poate "ajunge" doar in A). Dacă nu există nici un astfel de arc se trece la pasul 4.

Pasul 3. Se adaugă arcele găsite la pasul 2 la mulţimea A apoi se reia algoritmul de la pasul 2, pentru noua mulţime A.

Pasul 4. Dacă A conţine mulţimea tuturor nodurilor atunci graful nu conţine circuite. Dacă au rămas noduri în afara lui A atunci graful conţine circuite.

În general, algoritmii existenţi pentru determinarea drumurilor optime în grafuri se împart în două mari categorii: algoritmi pentru drumuri minime în grafuri orientate, respectiv algoritmi pentru drumuri maxime. Deasemeni, există două mari categorii de probleme şi anume:

- determinarea drumurilor optime de sursă unică (sursă unică, destinaţii multiple)- determinarea drumurilor optime între toate perechile de vârfuri (surse multiple, destinaţii

multiple)

5

Algoritmii prezentaţi în continuare sunt:

- Dijkstra: determină drumurile minime cu sursă unică în grafuri cu costuri nenegative- Dantzig: determină drumurile minime cu sursă unică în grafuri cu costuri nenegative- Bellman-Ford: drumuri minime cu sursă unică în grafuri care admit costuri negative, dar fără

circuite de cost negativ- determinarea drumurilor minime în grafuri orientate aciclice (din CLR)- Floyd-Warhall: drumuri minime între oricare două noduri- Bellman-Kalaba: drumuri maxime cu sursă unică şi număr fixat de paşi- Floyd-Warshall: drumuri maxime între oricare două noduri în grafuri fără circuite

Algoritmul lui Dijkstra

Problemă: Fiind dat un graf orientat G=(X,U), o funcţie l:UR+ şi un nod x0, să se determine pentru toate vârfurile xi pentru care există drum de la x0 la xi, lungimea celui mai scurt drum şi unul dintre drumurile minime de la x0 la xi.

Algoritmul utilizează metoda Greedy generând drumurile minime în ordinea crescătoare a lungimilor.

Exemplu: Pentru graful din figura alăturată, considerând nodul de plecare 1, se vor obţine în ordine:D1=(1,2) de lungime 1D2=(1,2,5) de lungime 2D3=(1,2,5,3) de lungime 4D4=(1,2,5,3,4) de lungime 5

De la 1 la 6 nu există drum.

Se porneşte din x0. Evident cel mai scurt drum de la x0 la unul din celelalte vârfuri ale grafului este dat de arcul (x0,xj) de lungime minimă. Următorul drum în ordinea lungimilor va fi dat fie de un alt arc cu extremitatea iniţială x0, fie de un drum (x0,xj,xp). Alegem în continuare drumuri în ordinea crescătoare a lungimilor, până când am determinat drumuri minime de la x0 către toate vârfurile pentru care există drum pornind din x0. Pentru aceasta se consideră S mulţimea vârfurilor xjÎX pentru

1

2

5

6

4

3

1

1

12

3

3

7

1

6

care am găsit drum minim de la x0 la xj. Iniţial S={x0}. La fiecare pas, adăgăm în S acel nod xkÎX-S cu proprietatea că drumul minim de la x0 la xk are cel mai mic cost dintre toate drumurile de la x0 la xp, cu xpÎX-S. Pentru exemplul considerat S va avea pe rând următorul conţinut:

S={1}S={1,2}S={1,2,5}S={1,2,5,3}S={1,2,5,3,4}

Se observă că drumul de la x0 la xk (nodul ce urmează să-l adăugăm în S la un moment dat) trece numai prin vârfuri din S (cu excepţia lui xk). Pentru a alege nodul xkÎX-S ce urmează a fi adăgat în S vom folosi un vector D=(d1,d2,...,dn) astfel încât:

lungimea drumului minim de la x0 la xi, dacă xiÎSdi= lungimea drumului minim de la x0 la xi ce foloseşte numai vârfuri din S, dacă xiS

Iniţial di=C(x0,i), ()i=1..n, adică este linia x0 din matricea costurilor. La un moment dat, adăgăm în S nodul xk cu proprietatea că dk=min{dj | xjÎX-S}. După adăgarea lui xk în S trebuie actualizate valorile lui d pentru elementele care nu sunt în S, deoarece este posibil ca drumul minim de la x0 la unul dintre aceste noduri (folosind noduri din S) să folosească nodul xk pe care tocmai l-am adăgat. Drumul minim de la x0 la xj ce foloseşte noduri din S (inclusiv xk) va fi de forma (x0,…,xk,xj). Deci pentru xjÎX-S, dj se modifică după adăugarea lui xk la S numai dacă dk+c(k,j)<dj, caz în care dj dk+c(k,j). În final, vectorul d va conţine costurile (lungimile) drumurilor minime de la x0 la celelalte noduri; dacă pentru un nod xj nu există drum de la x0 la xj, atunci dj=.

Pentru a reţine şi drumurile minime (nu numai lungimile lor) vom considera un vector numit T (tată) care reţine indicele precedentului fiecărui nod în drumul minim de la x0 la acel nod.Iniţial: 0 dacă i=x0 sau C(x0,i)=

Ti= x0 dacă C(x0,i) şi ix0

La fiecare actualizare de forma djDk+c(k,j) vom avea şi o actualizare a vectorului T de forma Tjk. Algoritmul se încheie când S conţine toate nodurile xj pentru care există drum de la x0 la xj, deci fie când S=X (dacă există drumuri de la x0 la toate celelalte noduri), fie când mulţimea X-S cuprinde numai noduri pentru care nu există drumuri pornind din x0 la ele (caz în care min{dj| xjÎX-S}=). Pentru reprezentarea mulţimii S se poate folosi vectorul caracteristic S cu n componente definit astfel: 0 dacă xiS Si=

1 dacă xiÎS

Algoritmul lui Dijkstra poate fi descris astfel:

algoritm Dijkstra(G,c,nod)Initializeaza_Sursa_Unica(G,nod)SQX(G)cat timp Q0 executa

uExtrage_Minim(Q)SS {u}

7

pentru fiecare v vecin cu u executaRelaxeaza(u,v,c)

sfarsit pentrusfarsit cat timp

unde:

Initializeaza_Sursa_Unica(G,nod)pentru fiecare vÎ X(G) executa

D[v] ∞T[v] 0

sfarsit pentruD[nod]0

După iniţializare avem T[v]=0 pentru orice nod vÎU, D[v]=0 pentru v=nod (nodul sursă) şi D[v]=∞ pentru vÎU-nod.

În procesul de relaxare al unui arc (u,v) se verifică dacă drumul minim la v , determinat până în acel moment, poate fi îmbunătăţit pe baza vârfului u, şi dacă da, atunci se reactualizează D[v] şi T[v]. Un pas de relaxare poate determina descreşterea valorii estimării drumului minim D[v] şi reactualizarea câmpului T[v] ce conţine predecesorul nodului v pe drumul minim. Pseudocodul următor realizează un pas de relaxare pe arcul (u,v).

Relaxeaza(u,v,c)daca D[v]D[u]+c(u,v) atunci

D[v]D[u]+c(u,v)T[v]u

sfarsit daca

Algoritmul Dijkstra operează prin menţinerea unei mulţimi S de noduri pentru care costurile finale corespunzătoare drumurilor minime de la sursa s au fost deja determinate, respectiv pentru toate nodurile vÎS avem D[v] egal cu distanţa mnimă. Algoritmul iterează selectarea unui nod uÎX-S pentru care estimarea drumului minim este minimă, introduce u în S şi relaxează arcele divergente din u. În algoritmul de mai sus Q este o coadă conţinând toate nodurile din X-S indexate prin valorile D corespunzătoare.

Exemplu: Considerăm graful anterior şi punctul x0=1. Cei trei vectori au valorile iniţiale:

D=(0, 1, , , 3, )T=(0, 1, 0, 0, 1, 0)S=(1, 0, 0, 0, 0, 0)

1) determinăm min(D[i]| S[i]=0)=> min=1, k=2 => S[2]1Actualizăm distanţele la nodurile neselectate încă.S[3]=0; D[3]=>D[2]+C[2,3]=1+7=8 => D[3]8, T[3]2S[4]=0; D[4]=, D[2]+C[2,4]=1+ , nu se poate actualizaS[5]=0; D[5]=3>D[2]+C[2,5]=1+1=2 => D[5]2, T[5]2S[6]= ; D[6]= , D[2]+C[2,6]=1+ , nu se poate actualizaDupă primul pas configuraţia celor trei vectori este:

D=(0, 1, 8, , 2, )T=(0, 1, 2, 0, 2, 0)S=(1, 1, 0, 0, 0, 0)

2) determinăm min(D[i]| S[i]=0) => min=2, k=5 => S[5]1Actualizăm distanţele la nodurile neselectate încă.S[3]=0; D[3]=8>D[5]+C[5,3]=2+2=4 => D[3]4, T[3]5S[4]=0; D[4]=, D[5]+C[5,4]=2+, nu se poate actualiza

8

S[6]=0; D[6]=, D[5]+C[5,6]=2+, nu se poate actualizaDupă al doilea pas configuraţia celor trei vectori este:

D=(0, 1, 4, , 2, )T=(0, 1, 5, 0, 2, 0)S=(1, 1, 0, 0, 1, 0)

3) determinăm min(D[i]| S[i]=0)=> min=4, k=3 => S[3]1Actualizăm distanţele la nodurile neselectate încă.S[4]=0; D[4]= > D[3]+C[3,4]=4+1=5 => D[4]5, T[4]3S[6]=0; D[6]= , D[3]+C[3,6]=4+, nu se poate actualizaDupă al treilea pas configuraţia celor trei vectori este:

D=(0, 1, 4, 5, 2, )T=(0, 1, 5, 3, 2, 0)S=(1, 1, 1, 0, 1, 0)

4) determinăm min(D[i]| S[i]=0)=> min=5, k=4 => S[4]1Actualizăm distanţele la nodurile neselectate încă.S[6]=0; D[6]=, D[4]+C[4,6]=5+, nu se poate actualizaDupă al patrulea pas configuraţia celor trei vectori este:

D=(0, 1, 4, 5, 2, )T=(0, 1, 5, 3, 2, 0)S=(1, 1, 1, 1, 1, 0)

5) determinăm min(D[i]| S[i]=0)=> min= şi algoritmul se încheie pentru că nu există nici-un drum de la nodul 1 la nodul 6

Programul care implementează algoritmul lui Dijkstra este următorul:

#include<iostream.h>#include<fstream.h>#define N 50#define INF 1<<15int c[N][N],D[N];int T[N],S[N],n,xp;void citire(){ ifstream f(„graf.in”);

int i,j,x,y,z;f>>n>>xp;//numarul de noduri si nodul de plecare//initializam matricea costurilorfor(i=1;i<=n;i++)

for(j=1;j<=n;j++) c[i][j]=INF;for(i=1;i<=n;i++) c[i][i]=0;while(!feof(f)){ f>.x>>y>>z; //arcul si costul sau

c[x][y]=z;}f.close();

}void minim(int& q){ int m,i;

m=2*INF;for(i=1;i<=n;i++)

if(!S[i]&&D[i]<m){

m=D[i]; q=i;}

}void determinare_drumuri()

9

{ int i,x,j,k,ok;//initializarifor(i=1;i<=n;i++){

D[i]=c[xp][i]; S[i]=0;if(c[xp][i]<INF) T[i]=xp;else T[i]=0;

}S[xp]=1; T[xp]=0; ok=1; x=0;do{ minim(k); //determina nodul k aflat la distanta minima

x++;if(D[k]==INF||x==n) ok=0; //nu mai pot construi drumuri minimeelse{

//actualizam vectorii S,T si DS[k]=1;for(j=1;j<=n;j++)

if(!S[j]&&D[j]>D[k]+c[k][j]){

D[j]=D[k]+c[k][j]; T[j]=k;}

}}while(ok);

}void drum(int i){ if(i)

{ drum(T[i]); cout<<i<<” ”; }}void afisare_drumuri(){ int i;

for(i=1;i<=n;i++)if(i!=xp)

if(D[i]==INF) cout<<"\nNu exista drum de la :”<<xp<<”la “<<i<endl;

else{cout<<"\nDrumul minim de la “<<xp<<”la “<<i<<”: ";drum(i); cout<<"\n";

cout<<"\tLungimea drumului este "<<D[i]<<endl;}

}void main(){ citire(); determinare_drumuri(); afisare_drumuri();}

Algoritmul lui Dantzig

Enunţ: Se consideră un graf orientat G=(X,U) şi o funcţie cost:UR+.Se desemnează un vârf de plecare p. Pentru orice vârf iÎX se cere determinarea tuturor drumurilor de la p la i care au costul minim.

Pentru rezolvarea acestei probleme sa va folosi algoritmul lui Dantzig. Acest algoritm obţine un graf parţial al lui G=(X,U) în care orice drum care pleacă din p este minim, În fapt, pe parcursul algoritmului se elimină arce ale grafului G, arce care nu participă la construirea nici unui drum de cost minim cu plecare din p.

10

Strategia algoritmului se bazează pe o parcurgere în lăţime a grafului G, adică selectarea nodurilor se face în ordinea apropierii lor de nodul p de plecare. Pe baza costurilor minime determinate succesiv, la fiecare pas al parcurgerii se identifică un nou nod, cel mai apropiat nod faţă de nodul p de plecare. Notăm cu k acest nod.

Urmează procesul de identificare a arcelor care se vor adăuga grafului parţial, deoarece acest proces conduce la obţinerea unor drumuri de la p la k cu costul minim determinat. Aceste arce respectă simultan condiţiile:

- au extremitatea iniţială într-un nod i deja selectat- au extremitatea finală în nodul k- d[i]+cost[i,k]=min (unde d[i] este distanţa minimă de la p la i şi cost[i,k] este cosul

arcului de la i la k)Algoritmul se opreşte când fie au fost selectate toate nodurile, fie când nu mai există drumuri de la p către vârfurile neselectate.

Considerăm ca exemplu graful următor:

Pasul 1: se selectează nodul 2, d[2]=2 şi se adaugă la graful parţial arcul (1,2)

Pasul 2: se selectează nodul 3, d[3]=3 şi se adaugă la graful parţial arcul (1,3)

3

1

2 4

6

5

2

2

2

2

1 1

1

4

7

3

1

2 4

6

5

2

11

Pasul 3: se selectează nodul 5, d[5]=3, se adaugă la graful parţial arcele (2,5) şi (3,5)

Pasul 4: se selectează nodul 4, d[4]=4, se adaugă la graful parţial arcele (2,4) şi (5,4)

Pasul 5: se selectează nodul 6, d[6]=6, se adaugă la graful parţial arcul (4,6)

3

1

2 4

6

5

2

2

3

1

2 4

6

5

2

2

1

1

3

1

2 4

6

5

2

2

1

1

1

2

12

Pentru exemplul considerat, costul minim de la 1 la 6 este 6 şi se obţine prin drumurile:1 2 4 61 2 5 4 61 3 5 4 6

Programul următor implementează algoritmul lui Dantzig. Complexitatea este O(n2).

#include<iostream.h>#include<fstream.h>#define N 50#define INF 1<<15int a[N][N],b[N][N],d[N],st[N],sos,p;int sel[N],n,min,k;void citire(){ ifstream f(„graf.in”);

int i,j,x,y,z;f>>n; //numarul de noduri //initializam matricea costurilor si matricea grafului partialfor(i=1;i<=n;i++)

for(j=1;j<=n;j++) { a[i][j]=INF; b[i][j]=INF; }for(i=1;i<=n;i++) { a[i][i]=0; b[i][i]=0; }

while(!feof(f)){ f>>x>>y>z;//arcul si costul sau

a[x][y]=z;}f.close();

}void minim(){ int i,j;

min=INF;for(i=1;i<=n;i++)

for(j=1;j<=n;j++)if(sel[i]&&!sel[j])

if(min>d[i]+a[i][j]){

min=d[i]+a[i][j]; k=j; }

}void dantzig()

3

1

2 4

6

5

2

2

1

1

1

2

2

13

{ int i,j;for(i=1;i<=n-1;i++){

minim();if(min!=INF){

sel[k]=1; d[k]=min;for(j=1;j<=n;j++)

if(sel[j]&&(d[j]+a[j][k]==min)) b[j][k]=a[j][k];}

}}void drum(int k){ int i,j;

for(i=1;i<=n;i++)if(b[st[k-1]][i]<INF && !sel[i]){

if(i!=sos){

sel[i]=1; st[k]=i; drum(k+1); sel[i]=0;}else{ for(j=1;j<k;j++) cout<<st[j];

cout<<sos<<" de cost “<<d[sos]<<”\n";}

}}void main(){ int i;

citire();cout<<"plecare: "; cin>>p;sel[p]=1; d[p]=0;dantzig();for(sos=1;sos<=n;sos++)

if(p!=sos){ for(i=1;i<=n;i++) sel[i]=0;

sel[p]=1; st[1]=p; drum(2); }}

Algoritmul Bellman-Ford

Enunţ: Se consideră un graf orientat G=(X,U) şi o funcţie de cost c:UR. Mulţimea X conţine n vârfuri. Se desemnează un nod p de plecare. Pentru orice nod jÎX se cere determinarea drumului de cost minim de la p la j. Se vor detecta situaţiile în care există circuite de cost negativ care includ nodul p.

Algoritmul Bellman-Ford determină drumurile de cost minim dintre un nod desemnat ca sursă (plecare) şi restul nodurilor accesibile lui chiar dacă există costuri negative pe arce. Aceste rezultate sunt furnizate numai în situaţia în care nodul de plecare nu face parte dintr-un circuit de cost negativ.

Strategia algoritmului este aceea de minimizare succesivă a costului drumului minim de la p la orice nod j din graf (d[j]) până la obţinerea costului minim.

Această operaţie se face prin verificarea posibilităţii ca fiecare arc (i,j)ÎU să participe la minimizarea distanţei de la p la j. Operaţia se face cu o trecere completă prin toate arcele grafului.

14

Condiţia ca distanţa de la p la j să poată fi minimizată prin arcul (i,j) este ca d[j]d[i]+c[i,j]Notăm cu n numărul de noduri din graf. Algoritmul efectuează n-1 treceri complete prin

mulţimea arcelor grafului (orice drum elementar poate fi format din maxim n-1 arce). În final, existenţa unui circuit negativ face ca la o nouă trecere prin mulţimea arcelor să fie în continuare posibilă minimizarea costului unui drum. În acest caz algoritmul evidenţiază prezenţa circuitului de cost negativ ce cuprinde nodul sursă.

Algoritmul pseudocod poate fi descris astfel:

algoritm Bellman_Ford(G,c,s)Initializeaza_Sursa_Unica(G,s)pentru i=1,n-1 executa

Relaxeaza(u,v,c)sfarsit pentru pentru fiecare arc (u,v)ÎU(G) executa

daca D[v]D[u]+c(u,v) atuncireturneaza FALS

sfarsit dacasfarsit pentrureturneaza ADEVARAT

Funcţiile Initializeaza_Sursa_Unica() şi Relaxeaza() sunt cele prezentate la algoritmul lui Dijkstra. Ca şi algoritmul lui Dijkstra, algoritmul Bellman_Ford utilizează tehnica de relaxare, procedând la descreşterea estimării D[v] a drumului minim de la sursa s la fiecare nod vÎX până când este obţinut costul adevărat corespunzător unui drum minim. Algoritmul returnează ADEVARAT dacă şi numai dacă graful nu conţine circuite de cost negativ accesibile din sursa s.

În situaţia în care graful este memorat în liste de adiacenţă complexitatea algoritmului este O(n*m).

În programul următor, funcţia minimizeaza() efectuează o trecere completă prin toate arcele grafului în vederea descreşterii costurilor drumurilor cu plecare din nodul sursă desemnat prin start.

#include<iostream.h>#include<fstream.h>#include<stdlib.h>#define N 50#define INF 32000

j

i

p

d[i]

d[j]

c[i,j]

15

typedef struct nod{int inf; //vecinul int c; //costul muchieinod *leg; //adresa urmatorului vecin

}LST;LST *lc[N]; //listele de adiacenta (vecini)int t[N],d[N],n,start;void citire(){

ifstream f(„graf.in”);LST *x;int i,j,co;f>>n;for(i=1;i<=n;i) //aloca adrese pentru listele de vecini{

lc[i]=new LST; lc[i]->leg=0;}while(!feof(f)){

f>>i>>j>>co;x=new LST; x->inf=j; x->c=co;x->leg=lc[i]->leg; lc[i]->leg=x; //adaug pe j in lista vecinilor lui i

}f.close();

}int minimizeaza(){

int ok=0,j;LST *p;for(j=1;j<=n;j){

p=lc[j]->leg;while(p){

if(d[p->inf]>d[j]>c){

ok=1; d[p->inf]=d[j]>c; t[p->inf]=j;}p=p->leg;

}}return ok;

}void bellman_ford(){

int ok,i;for(i=1;i<=n;i){

t[i]=0; d[i]=INF; //initializari}d[start]=0;for(i=1;i<=n-1;i) ok=minimizeaza();ok=minimizeaza(); //a n-a trecere va depista circuite de cost

negativif(ok)

16

{cout<<"\nCircuit de cost negativ\n";exit(0);

}}void drum(int x){

if(x){

drum(t[x]); cout<<x;}

}void main(){

int i;citire();cout<<"plecare: "; cin>start;bellman_ford();for(i=1;i<=n;i)

if(i!=start){

cout<<"cost “<<d[i]<<” prin ";drum(i); cout<<"\n";

}}

Drumuri minime în grafuri orientate aciclice

Prin relaxarea muchiilor unui graf orientat aciclic ponderat G=(X,U) cu n noduri şi m arce, putem determina drumurile minime de sursă unică în timp O(n+m). Drumurile minime sunt totdeauna bine definite într-un astfel de graf datorită faptului că acesta nu poate avea cicluri negativ, chiar dacă graful conţine arce de cost negativ.

Algoritmul începe prin sortarea topologică a grafului pentru impunerea unei ordini liniare a nodurilor. Dacă există drum de la nodul u la nodul v atunci u precede v în ordinea topologică. În continuare, se efectuează o singură trecere peste nodurile sortate topologic şi pe măsură ce fiecare vârf este procesat, sunt relaxate toate muchiile divergente din acel vârf.

În următorul algoritm s este nodul sursă, graful are n noduri şi este reprezentat prin matricea costurilor cnxn, d este vectorul distanţelor minime determinate, T este vectorul predecesorilor.

algoritm GOA_drumuri_minim(G,c,s)sorteaza in ordine topologica varfurile din GInitializeaza_Sursa_Unica(G,s)pentru fiecare nod u in ordinea data de sortarea topologica executa

pentru fiecare nod v vecin cu u executaRelaxaza(u,v,c)

sfarsit pentrusfarsit pentru

Sortarea topologică se realizează cu ajutorul parcurgerii în adâncime DF. În momentul în care explorarea unui nod i s-a încheiat, el este introdus la începutul unei liste. Lista este realizată în vectorul m care va fi completat de la sfârşit spre început, în ordinea inversă a timpilor de încheiere a explorării unui nod. În continuare, ordinea topologică este dată de valorile din vectorul m.

17

Funcţiile Initializeaza_Sursa_Unica() şi Relaxaza(u,v,c) au aceeaşi semnificaţie ca la algoritmul lui Dijkstra.

Programul următor implementează algoritmul descris mai sus:

#include<iostream.h>#include<fstream.h>#define N 50#define INF 32000typedef struct nod{

int inf;nod *leg;

}AD;AD *L[N]; //listele vecinilorint c[N][N],viz[N],m[N],T[N],d[N],n,k,s;void citire(){ int i,j,co; AD *x;

ifstream f(„graf.in”);f>>n; for(i=1;i<=n;i++) //initializare matrice costuri{

for(j=1;j<=n;j++) c[i][j]=INF;c[i][i]=0;

}for(i=1;i<=n;i++) //initializare liste vecini{

L[i]=new AD; L[i]->leg=0;}

while(!feof(f)){

f>>i>>j>>co;c[i][j]=co; x=new AD; x->inf=j;x->leg=L[i]->leg; L[i]->leg=x;//adaug j in lista vecinilor lui i

}f.close();

}void Init(){

int i;for(i=1;i<=n;i++){

viz[i]=0; m[i]=0;}k=n;

}void DF(int i){

AD *x=L[i]->leg; //lista vecinilor lui iviz[i]=1; while(x){

if(!viz[x->inf]) DF(x->inf);x=x->leg;

}//i a fost complet explorat, il adaug la inceputul listei mm[k]=i; k--; //m contine nodurile in ordine topologica

18

}void Parcurge(){

int i;Init();for(i=1;i<=n;i++)

if(!viz[i]) DF(i);}void Initializare(int s) //nodul sursa{

int i;for(i=1;i<=n;i++) //pentru fiecare nod din graf{

d[i]=INF; //nu s-a determinat nici-un drum de la s la v, cost infinitT[i]=0; //nodul tata pe drumul minim de la s la v

}d[s]=0; //pentru nodul sursa

}

void Relaxeaza(int u,int v) //relaxeaza arcul (u,v){

if(d[v]>d[u]+c[u][v]){

d[v]=d[u]+c[u][v]; T[v]=u;}

}void GOA_drum(int s){

int i; AD *x;Parcurge(); //realizeaza sortarea topologica in vectorul mInitializare(s);for(i=1;i<=n;i++) //pentru fiecare nod in ordinea data de sortarea topologica{

x=L[m[i]]->leg; //parcurg lista vecinilor lui m[i]while(x){

Relaxeaza(m[i],x->inf);x=x->leg;

}}

}void drum(int i){

if(i!=s){

drum(T[i]); cout<<"%d ",i);}else cout<<"%d ",s);

}void main(){

int i;citire(); cout<<"nodul sursa: "; cin>.s;GOA_drum(s);

19

for(i=1;i<=n;i++)if(m[i]!=s)

if(d[i]<INF){

cout<<"de la “<<s<<”la “<<m[i]<<” cost “<<d[m[i]]<<” drum: “;drum(m[i]); cout<<"\n";

}else cout<<"nu exista drum de la “<<s<<” la ”<<m[i];

}

Algoritmul Floyd-Warshall

Enunt: Fiind dat un graf orientat G=(X,U) cu X={x1,x2,….,xn} şi o funcţie de cost l:UR+

să se determine pentru fiecare pereche de noduri xi,xj (ij) lungimea minimă a drumurilor de la xi la xj precum şi aceste drumuri (în caz că există drumuri de la xi la xj).

Algoritmul Floyd-Warhall determină lungimile minime ale drumurilor între oricare două noduri ale grafului într-o matrice C=(cij)nxn unde :

lungimea drumului minim de la xi la xj dacă există drum de la xi la xj cij= 0 dacă i=j dacă nu există drum de la xi la xj

Determinarea matricii C este asemănătoare algoritmului Roy-Warshall pentru obţinerea matricii drumurilor. Se porneşte de la matricea costurilor ataşată grafului. Algoritmul este :

pentru k=1,n pentru i=1,n pentru j=1,n cij=min(cij,cik+ckj) sf_pentru sf_pentrusf_pentru

Simultan cu determinarea lungimilor minime ale drumurilor, pot fi reţinute şi nodurile care formează drumurile. Vom folosi o matrice D=(dij)nxn ale cărei elemente dij sunt mulţimi de noduri. Elementul dij va reprezenta în final mulţimea nodurilor ce pot precede pe xj în drumul minim de la xi la xj. Odată cu iniţializarea matricii C cu matricea costurilor, vom iniţializa şi matricea D astfel:

{xi} dacă cij< şi ijdij=

dacă cij= sau i=j Pe măsură ce se actualizează matricea C vom actualiza şi matricea D după cum urmează:

- dacă cij<cik+ckj , atunci dij rămâne neschimbat- dacă cij=cik+ckj (înseamnă că am găsit noi posibilităţi de construire a drumului minim de la

xi la xj folosind nodul k) se adaugă la dij nodurile din dkj

- dacă cij>cik+ckj se iniţializează dij cu dkj

În final reconstituirea drumurilor minime între oricare două vârfuri xi,xj se face pornind din xj astfel: precedentul lui xj îl alegem din mulţimea dij având unul din aceste noduri fixat (să-l numim xq), precedentul acestuia va fi orice nod din mulţimea diq. Procedeul continuă până ajungem la nodul xi.

20

Observaţie: Dacă ne interesează doar câte un drum pentru fiecare pereche de noduri xi,xj vom considera în locul matricii D o matrice D’ tot nxn astfel încât d’

ij să reţină un nod ce-l poate precede pe xj în drumul minim de la xi la xj. În acest caz, algoritmul Floyd-Warshall este următorul:

pentru k=1,n pentru i=1,n pentru j=1,n daca cij>cik+ckj

atunci cij=cik+ckj

dij=k sf_daca

sf_pentru sf_pentrusf_pentru

Complexitatea algoritmului este de ordinul O(n3). Programul următor implementează algoritmul în varianta de mai sus.

#include<iostream.h>#include<fstream.h>

#define N 50#define INF 1<<15int C[N][N]; //initial matricea costurilor,apoi a costurilor drumurilorint D[N][N]; //pe linia d[i,j]=nodul care poate precede nodul j // pe drumul minim de la nodul i la nodul jint n,m; void INITC()//initializeaza matricea costurilor C{

int i,j,x1,x2,cost;ifstream f(„graf.in”);f>>n>>m;for(i=1;i<=n;i++){

for(j=1;j<=n;j++) C[i][j]=INF;C[i][i]=0;

}for(i=1;i<=m;i++){

f>>x1>>x2>>cost;C[x1][x2]=cost;

}f.close();

}void Drum(int i,int j)//afiseaza un drum de la i la j pornind de la nodul j{

if(j){ Drum(i,D[i][j]);

cout<<j<<” ”;}

}void AFISARE()//afisarea rezultatelor{

21

int i,j;for(i=1;i<=n;i++)

for(j=1;j<=n;j++){

if(C[i][j]==INF)cout<<"\nnu exista drum intre “<<i<<” si “<<j<<endl;

elseif(i!=j){

cout<<"\ncost drum de la “<<i<<” la “<<j<<”este ”<<C[i][j];cout<<"\tsuccesiunea de varfuri este: ";cout<<i<<” ”; Drum(i,j);

}}

}void main(){

int i,j,k;INITC();for(k=1;k<=n;k++)

for(i=1;i<=n;i++)for(j=1;j<=n;j++)

if(C[i][k]<INF&&C[k][j]<INF)if(C[i][j]>C[i][k]+C[k][j]){

C[i][j]=C[i][k]+C[k][j];D[i][j]=k;

}AFISARE();

}

Algoritmul Floyd-Warshall pentru drumuri de cost maxim

Fie G=(X,U) un graf orientat fără circuite cu X=(x1,x2,...,xn) şi l:UR+ funcţia de cost ataşată grafului. Ne punem problema determinării drumurilor de lungime maximă în acest graf. Pentru rezolvarea acestei probleme vom considera graful reprezentat prin matricea costurilor în forma b), adică prin matricea C=(cij)nxn cu

l(xi,xj) dacă (xi,xj)ÎU

cij= 0 dacă i=j - dacă (xi,xj)U

Algoritmul Floyd-Warshall de determinare a drumurilor minime poate fi adaptat cu mici modificări pentru determinarea drumurilor maxime între oricare două noduri xi,xj (ij). Pentru a reţine nodurile prin care trec aceste drumuri maxime vom folosi matricea D=(dij)nxn în care:

{xi} dacă cij>- şi ij dij= dacă cij=- sau i=j

22

Matricile C şi D se modifică conform următorului algoritm:

pentru k=1,n pentru i=1, n (ki) pentru j=1,n (kj) daca cij<cik+ckj

atunci cijcik+ckj

dijdkj altfel daca cij=cik+ckj

atunci dijdijdkj sf_daca sf_daca sf_pentru sf_pentrusf_pentru

În matricea C vom avea în final lungimile drumurilor maxime între oricare două noduri, iar în dij vom avea mulţimea nodurilor ce pot precede pe xj într-un drum maxim de la xi la xj. Programul pentru determinarea tuturor drumurilor maxime între oricare două vârfuri ale unui graf G=(X,U) este analog celui de la problema anterioară; se foloseşte acelaşi algoritm ,adaptat noilor cerinţe.

Algoritmul Bellman-Kalaba

Enunţ: Se consideră un graf orientat G=(X,U) conex, fără circuite şi o funcţie de cost a:UR. Desemnându-se un nod x, se cere determinarea drumurilor de cost maxim de la toate celelalte noduri la el, drumuri care includ un număr impus de arce (paşi).

Pe baza matricii costurilor grafului considerat, algoritmul construieşte o nouă matrice c în care pe coloana j (j≤n) se vor afla costurile maxime ale drumurilor ce ajung în x folosind j arce. Astfel c[i,j] reprezintă costul maxim al unui drum de la i la x şi trece prin j arce.

Iniţial, matricea c va conţine pe prima coloană costul arcelor spre nodul x, deci drumuri de lungime 1. A doua iteraţie va determina costurile maxime ale drumurilor ce ajung în x şi conţin două arce. Ele se vor memora în a doua coloană şi se vor determina pe baza valorilor din coloana anterioară.

Astfel, pentru determinarea valorii c[i,2] vom adăuga pe rând arcele ce pleacă din i către drumurile de lungime 1 anterior determinate. Se va identifica valoarea maximă dintre acestea: c[i,2]=max(c[j,1]+a[i,,j]│jÎX).

23

Generalizând, pentru a determina costul maxim al drumului de la i la x folosind k arce se calculează: max(c[j,k-1]+a[i,j]│jÎX).

Numerele de pe fiecare linie a matricei c vor forma un şir monoton. Algoritmul se încheie în momenul în care valorile situate pe două coloane consecutive sunt identice, deci când nici un drum nu se poate maximiza. Faptul că nu există circuite în graf ne asigură că numărul maxim de iteraţii ar putea fi egal cu n-1 (n numărul de noduri). Complexitatea algoritmului este O(n3).

Exemplu: Considerăm graful din figură şi determinăm drumurile maxime ce ajung în nodul x=6.

Notăm cu c(i) coloana i din matricea c a drumurilor maxime ce ajung în x=6 folosind i arce. Algoritmul se încheie la iteraţia 5 deoarece c(4)=c(5).

c(1) c(2) c(3) c(4) c(5)

-1 -1 10 14 14-1 8 12 12 12-1 8 8 8 82 2 2 2 2

i

x

j

c[i,k-1]

a[i,j]

1

1

2

3 5

4

61

1

7

2

2

2

2

4

24

7 7 7 7 70 0 0 0 0

#include<iostream.h>#include<fstream.h>#define N 50int a[N][N],c[N][N];int pasi,p1,n,x;unsigned char t[N][N];void citire(){

ifstream f(„graf.in”);int i,j,x,y,z;cin>>n; //numarul de noduri //initializam matricea costurilor si matricea grafului partialfor(i=1;i<=n;i++)

for(j=1;j<=n;j++) a[i][j]=-1; //pentru arcele lipsafor(i=1;i<=n;i++) a[i][i]=0; while(!feof(f)){

f>>x>>y>z;//arcul si costul saua[x][y]=z;

}f.close();

}void initializari(){

int i,j;for(i=0;i<=n;i++)

for(j=0;j<=n;j++) { c[i][j]=-1; t[i][j]=0; }for(j=1;j<=n;j++){

c[j][1]=a[j][x];if(c[j][1]!=-1) t[j][1]=j;

}}void kalaba(){

int i,j,ok,k;k=2;do{

for(i=1;i<=n;i++)for(j=1;j<=n;j++)

if(a[i][j]!=-1 && c[j][k-1]!=-1)if(c[i][k]<c[j][k-1]+a[i][j]){ c[i][k]=c[j][k-1]+a[i][j]; t[i][k]=j; }

ok=1;for(i=1;i<=n;i++)

if(c[i][k-1]!=c[i][k]) { ok=0; break; }k++;

}while(!ok);}void drum(int x,int y){

cout<<x<<” ”;

25

if(y!=1) drum(t[x][y],y-1);}void scrie(){

if(c[p1][pasi]!=-1){

while(c[p1][pasi]==c[p1][pasi-1]) pasi--;cout<<"drum maxim “<<p1<<” -> “<<x<<” prin “<<pasi<<”arce\n";

cout<<"costul “<<c[p1][pasi]<<endl;drum(p1,pasi); cout<<x<<endl;

}else cout<<"nu exista\n";

}void main(){

citire(); cout<<"plecare: "; cin>.p1; cout<<"sosire: "; cin>.x; cout<<"numar pasi: "; cin>>pasi;

initializari(); kalaba(); scrie();}

26

Drumuri minime în labirint

Enunţ: Se consideră un labirint codificat sub forma unei matrici de n*n caractere reprezentând camerele labirintului. Caracterul „o” semnifică o cameră liberă, iar caracterul „*” o cameră ocupată. Matricea este dată în fişierul lab.in, prima linie a acestuia conţinând dimensiunea n a labirintului. Dându-se o cameră de plecare (xi,yi) şi o cameră de sosire (xf,yf), evident neocupate, să se determine cel mai scurt drum de la camera de plecare până la camera de sosire ştiind că dintr-o cameră liberă ne putem deplasa într-o altă cameră vecină liberă aflată la stânga, la dreapta, deasupra sau dedesubtul camerei curente.

Citirea labirintului din fişier se face prin crearea unei matrici L astfel: 0, dacă avem cameră ocupată, adică *L[i,j]= 1, dacă avem cameră liberă, adică o

Vom ataşa acestei probleme un graf neorientat cu n*n noduri reprezentând camerele labiruntului, ele fiind numerotate în ordine 1,2,..,n*n. Dacă două camere sunt libere şi învecinate, atunci în graf cele două noduri vor fi adiacente. Vom memora graful prin matricea costurilor A în care costul unei muchii este 1.Pe baza matricii L şi a regulilor de vecinătate din enunţ vom construi matricea costurilor A de dimensiune n*n astfel:

- se iniţializează matricea A cu o valoare foarte mari (infinit)- cum avem n*n camere, la generarea matricii costurilor ne vom referi la configuraţia

labiruntului astfel: nodul i din graf corespunde camerei (x=(i-1)/n+1,y=(i-1)%n+1) din labirint (relaţii obţinute prin liniarizarea matricii L)

- reciproc, nodul reprezentat de (x,y) este elementul p=n*(x-1)+y din matricea L.În acest fel se verifică toate camerele libere vecine şi se completează matricea costurilor.

Pentru a determina cel mai scurt drum între camera de plecare şi cea de sosire vom folosi algoritmul Floyd-Warshall. Pentru a afişa efectiv camerele de pe drumul minim determinat de la nodul sursa nod_i la destinaţia nod_f vom folosi strategia Divide et Impera, considerând că dacă avem un nod intermediar k şi A[nod_i,nod_f]=A[nod_i,k]+A[k,nod_f], atunci nodul k se află pe drumul optim căutat, deci vom genera drumurile (nod_i,k) şi (k,nod_f). Complexitatea acestei metode este dată de complexitatea algoritmului Floyd-Warhall adică este O((n*n)3) , inacceptabilă pentru valori n chiar relativ mici.

Programul următor implementează metoda descrisă mai sus.#include<iostream.h>#include<fstream.h>#define N 15#define INF 10000short int L[N][N],A[N*N][N*N],n;void citire(){

ifstream f("lab.in";char s[20]; int i,j;f>>n; fgetc(f);for(i=1;i<=n;i++){

fgets(s,20,f); for(j=0;j<n;j++)

if(s[j]=='*') L[i][j+1]=0;else L[i][j+1]=1;

}

27

f.close();for(i=1;i<=n;i++){

for(j=1;j<=n;j++) cout<<L[i][j]<<”\t”;cout<<"\n";

}}void construieste_graf(){

int i,j,x,y;for(i=1;i<=n*n;i++) //initializam matricea costurilor

for(j=1;j<=n*n;j++) A[i][j]=INF;for(i=0;i<=n+1;i++) //bordam matricea L cu 0

L[0][i]=L[i][0]=L[i][n+1]=L[n+1][i]=0;for(i=1;i<=n*n;i++){

x=(i-1)/n+1; y=(i-1)%n+1;if(L[x][y]==1) {

if(L[x][y-1]==1) //la stangaA[n*(x-1)+y-1][i]=A[i][n*(x-1)+y-1]=1;

if(L[x][y+1]==1) //la dreaptaA[n*(x-1)+y+1][i]=A[i][n*(x-1)+y+1]=1;

if(L[x-1][y]==1) //deasupraA[i][n*(x-2)+y]=A[n*(x-2)+y][i]=1;

if(L[x+1][y]==1) //dedesubtA[i][n*x+y]=A[n*x+y][i]=1;

}A[i][i]=0;

}}void Floyd_Warhall(){

int i,j,k;for(k=1;k<=n*n;k++)

for(i=1;i<=n*n;i++)for(j=1;j<=n*n;j++)

if(A[i][j]>A[i][k]+A[k][j]) A[i][j]=A[i][k]+A[k][j];}void drum(int x,int y){

int k=1,gata=0;while(k<=n*n && !gata){

if(x!=k && y!=k && A[x][y]==A[x][k]+A[k][y]){

drum(x,k); drum(k,y); gata=1;}k++;

}if(!gata) cout<<y<<” ”;

}void afisare_drum(int x,int y){

if(A[x][y]<INF){

28

cout<<"\nlungime=”<,A[x][y];cout<<"prin celulele: “x; drum(x,y);

}else cout<<"\nNu exista drum\n";

}void main(){

int xi,yi,xf,yf,nod_i,nod_f;citire(); construieste_graf(); cout<<"punctul de plecare (x,y)="; cin>>xi>>yi;cout<<"punctul de sosire (x,y)="); cin>>xf>>yf;nod_i=n*(xi-1)+yi; nod_f=n*(xf-1)+yf;Floyd_Warhall(); afisare_drum(nod_i,nod_f); cout<<"\n";

}

Observaţie: Complexitatea algoritmul devine O(n2) dacă în loc de algoritmul Floyd-Warshall folosim o parcurgere BF a grafului reprezentat prin liste de adiacenşă şi ataşăm nodurilor un vector de marcare (algoritmul lui Lee).

Programul următor determină drumul minim între camera de plecare nod_i şi camera de sosire nod_f folosind pentru graful asociat listele de adiacenţă alocate dinamic. Tablourile utilizate de parcurgerea BF sunt deasemenea alocate dinamic în heap pentru a mări spaţiul de memorie disponibil.

#include<iostream.h>#include<fstream.h>#define N 50typedef struct nod{

short int inf;nod *leg;

}AD;AD *LA[N*N];short int L[N][N],n;short int *C,*T,*VIZ,*DMIN; //tablouri alocate dinamic in heapvoid citire(){

ifstream f(“lab.in");char s[20]; int i,j;cin>>n; f.getc(f);cout<<"\tLabirintul este:\n";for(i=1;i<=n;i++){

f.gets(s,20,f); puts(s);for(j=0;j<n;j++)

if(s[j]=='*') L[i][j+1]=0;else L[i][j+1]=1;

}f.close();

}void Init() //aloca spatiu pentru tablourile C,T,VIZ,DMIN{

int i;C=new short int [n*n+1];T=new short int [n*n+1];VIZ=new short int [n*n+1];for(i=1;i<=n*n;i++) VIZ[i]=0; //initializam vectorul de vizitare

29

DMIN=new short int [n*n+1];}void construieste_graf(){

int i,x,y;AD *p;for(i=1;i<=n*n;i++) {

LA[i]=new AD; LA[i]->leg=0;}for(i=0;i<=n+1;i++) //bordam matricea L cu 0

L[0][i]=L[i][0]=L[i][n+1]=L[n+1][i]=0;for(i=1;i<=n*n;i++){

x=(i-1)/n+1; y=(i-1)%n+1;if(L[x][y]==1) {

if(L[x][y-1]==1) //vecin la stanga{

p=new AD; p->inf=n*(x-1)+y-1; p->leg=LA[i]->leg;LA[i]->leg=p;p=new AD; p->inf=i; p->leg=LA[n*(x-1)+y-1]->leg;LA[n*(x-1)+y-1]->leg=p;

}if(L[x][y+1]==1) //vecin la dreapta{

p=new AD; p->inf=n*(x-1)+y+1; p->leg=LA[i]->leg; LA[i]->leg=p;

p=new AD; p->inf=i; p->leg=LA[n*(x-1)+y+1]->leg;LA[n*(x-1)+y+1]->leg=p;

}if(L[x-1][y]==1) //vecin deasupra{

p=new AD; p->inf=n*(x-2)+y; p->leg=LA[i]->leg; LA[i]->leg=p;p=new AD; p->inf=i; p->leg=LA[n*(x-2)+y]->leg;LA[n*(x-2)+y]->leg=p;

}if(L[x+1][y]==1) //vecin dedesubt{

p=new AD; p->inf=n*x+y; p->leg=LA[i]->leg; LA[i]->leg=p;p=new AD; p->inf=i; p->leg=LA[n*x+y]->leg; LA[n*x+y]->leg=p;

}}

}}void BF(int nod,int s){

AD *x; int prim,ultim;VIZ[nod]=1; T[nod]=0; DMIN[nod]=0;prim=ultim=1; C[prim]=nod;while(prim<=ultim){

nod=C[prim]; //extrag nodul din varful cozii

30

x=LA[nod]->leg; //lista vecinilor lui nodwhile(x){

if(!VIZ[x->inf]){

T[x->inf]=nod; VIZ[x->inf]=1;DMIN[x->inf]=DMIN[nod]+1;if(x->inf==s) return; //am ajuns in punctul de sosire, opresc parcurgereaC[++ultim]=x->inf; //adaug x->inf in coada

}x=x->leg;

}prim++; //avansez la urmatorul nod din coada

} }void drum(int i,int nod){

if(i!=nod) drum(T[i],nod);cout<<i<<” ”;

}void main(){

int xi,yi,xf,yf,nod_i,nod_f;citire(); construieste_graf(); Init();cout<<"punctul de plecare (x,y)="; cin>>xi>>yi;cout<<"punctul de sosire (x,y)="; cin>>xf>>yf;nod_i=n*(xi-1)+yi; nod_f=n*(xf-1)+yf;BF(nod_i,nod_f); //parcurg BF graful din nodul de plecareif(DMIN[nod_f]){cout<<"\nlungime=”<< DMIN[nod_f]<<”este ”<<drum(nod_f,nod_i)<<” \

ndrum prin nodurile: ";,cout<<"\n";

}else

cout<<"\nNu exista drum intre camera “<<nod_i<<“ si camera “<<nod_f<<endl;}

31

Bibliografie

1. Thomas H. Cormen, Charles E. Leiserson, Ronald R. Rivest, Introducere in algoritmi, Editura Agora, 2000

2. Daniela Oprescu, Liana Bejan Ienulescu, Viorica Patrascu, Informatica - Manual pentru clasa a XI-a, Editura Niculescu, 2001

3. George Daniel Mateescu, Pavel Florin Moraru, Informatica - Manual pentru clasa a XI-a, Editura Niculescu 2003

4. Dana Lica, Doru Popescu Anastasiu, Radu Boriga, Dan Pracsiu, Fundamentele programarii- Culegere de probleme pentru clasele IX-XI, Editura L&S Soft 2002

5. Carpen Manuela, Suport de curs si lucrari de laborator, manuscris

32