Extras din curs

Drumuri minime intr-un graf

Fiind dat un graf G=(V,E) orientat se considera o functie asociata w:E->X numita functie de cost.

Costul unui drum u..v este reprezentat de suma costurilor muchiilor de pe drumul u..v. De exemplu pentru graful din figura 1 exista mai multe drumuri intre nodurile 1 si 2:

- Drumul 1->2 ce are cost total w(1,2)=1;

- Drumul 1->3->5->2 ce are w(1,2)=2+8+7=17;

- Drumul 1->3->4->6->5->2 ce are w(1,2)=2+5+6+4+7=24;

- Drumul 1->6->5->2 ce are w(1,2)=3+4+7=14;

Scopul nostru este sa determinam drumul optim din punct de vedere al costului intre o sursa s si toate nodurile d unde dÎV. In cazul in care dÏR(s), distanta dintre s si d va fi considerata infinita.

In functie de codomeniul X al functiei de cost w distingem cateva cazuri distincte. Vom vedea ca exista algoritmi diferiti pentru cazurile de mai jos.

1. X=[0,) – muchiile au costuri pozitive

Figure 1 Graf cu muchii pozitive

Un exemplu de astfel de graf este o harta a unui oras unde sunt specificate distantele dintre diferitele intersectii

2. X=R – muchiile au costuri reale si nu exista cicluri de cost negativ

Un exemplu de astfel de graf poate sa apara in reprezentarea unor activitati economice unde pot sa apara muchii de cost negativ in cazul unor pierderi financiare

Figure 2 graf cu muchii reale dar fara ciclu de cost negativ

3. X=R – muchiile au costuri reale si exista cicluri de cost negativ

Figure 3 graf cu muchii reale si cu ciclu de cost negative

Prin ciclu de cost negativ intelegem un ciclu in care suma costurilor muchiilor ce fac parte din drum este negativa. In figura de mai sus drumul 1->3->4->1 are cost negativ. Se observa ca suma costurilor muchiilor de pe acest drum este negativa (2+5+(-2))=-1. Datorita acestui ciclu nu se poate obtine un cost minim pentru drumul (1,2) de exemplu deoarece la fiecare parcurgere a drumului de cost negativ costul drumului (1,2) mai scade cu o unitate. Astfel dupa n parcurgeri costul drumului (1,2) va fi n-2.

Algoritmul lui Dijkstra

Algoritmul lui Dijkstra se foloseste numai pentru grafuri orientate G=(V,E) pentru care exista o functie de cost asociata w:E->[0, ) – cazul 1 din cele prezentate de mai sus.

Algoritmul lui Dijkstra este un algoritm de tip Greedy. Optimul local ce se cauta este reprezentat de distanta dintre un nod sursa si un nod destinatie – distanta care este initializata cu infinit si apoi imbunatatita la fiecare pas. Imbunatatirea unei distante este realizata printr-un proces numit relaxare si functionarea acestui proces va fi exemplificata pe baza grafului din figura 4.