Drumuri Minime de Sursa Unica intr-un Graf

Curs
7.5/10 (4 voturi)
Domeniu: Automatică
Conține 1 fișier: doc
Pagini : 6 în total
Cuvinte : 1092
Mărime: 121.16KB (arhivat)
Cost: Gratis
Profesor îndrumător / Prezentat Profesorului: Vlad Posea

Extras din document

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.

Preview document

Drumuri Minime de Sursa Unica intr-un Graf - Pagina 1
Drumuri Minime de Sursa Unica intr-un Graf - Pagina 2
Drumuri Minime de Sursa Unica intr-un Graf - Pagina 3
Drumuri Minime de Sursa Unica intr-un Graf - Pagina 4
Drumuri Minime de Sursa Unica intr-un Graf - Pagina 5
Drumuri Minime de Sursa Unica intr-un Graf - Pagina 6

Conținut arhivă zip

  • Drumuri Minime de Sursa Unica intr-un Graf.doc

Alții au mai descărcat și

Proiectarea unui Circuit de Comanda pentru un Motor Pas cu Pas

I. DATE INIŢIALE Tipul motorului pas cu pas: cu reluctanţă variabilă Curentul nominal: I = 3A Tensiunea de alimentare: U = 50V Secvenţa de...

Prezentarea Metodei Celor Mai Mici Pătrate

Metodele numerice care se folosesc astăzi, fie cele clasice, fie cele noi, se utilizează numai prin intermediul calculatorului. Ţinând cont de...

Pendulul Inversat

a) Ipoteze de modelare: i) Pendulul inversat este montat pe un carucior actionat de un motor de curent continuu. ii) Masa pendulului este...

Grile Rezolvate Automatica

1. Procesorul reprezinta: a) unitatea de prelucrare aritmetica si logica b) unitatea de realizare a prelucrarilor aritmetice c) reuniunea...

Algoritmul lui Dijkstra pentru Calculul Tuturor Drumurilor de Cost Minim

Prezentarea algoritmului standard Algoritmul Dijkstra este un algoritm care calculeaza drumurile minime de la un nod al unui graf la toate...

Fundamentele Conditionarii Semnalelor pentru Sistemele de Achizitii de Date pe Baza de Calculatoare

Acest referat prezinta fundamentele folosirii hardware-lui de conditionare a semnalului folosit cu sistemele DAQ pe baza de calculatoare. Sunt...

Java

Java este o tehnologie inovatoare lansata de compania Sun Microsystems 1n 1995, care a avut un impact remarcabil asupra a1ntregii comunitatsi a...

Tranzistorul cu Efect de Camp (TEC)- Field Effect Transistor - FET

TRANZISTORUL CU EFECT DE CÂMP ("TEC")-"Field Effect Transistor" ("FET") E un tranzistor uni-polar (cu purtatori de sarcina de un singur tip, n sau...

Ai nevoie de altceva?