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

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...

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...

Dispozitive si Circuite Electronice - Teoria Reactiei Negative - Amplificatoare TRN

Amplificatoare cu reactie negativa Schema bloc generala - prezentata alaturat - contine elemente idealizate, unilaterale, cu sensurile de...

UML

Caz Orasul Lincoln din statul Nebraska era acum o suta de ani, primul oras din vest care a trecut în proprietatea municipalitatii serviciile...

Modelarea Datelor

2. MODELAREA DATELOR Posibilitatea de a obtine informatii utile dintr-o colectie de date (deci dintr-o baza de date) depinde de modul de...

Limbaje Formale - Curs 1

1. Introducere in limbaje formale. Definitii 2. Operatii pe limbaje 3. Expresii regulate 1. Introducere in limbaje formale. Definitii....

Arhitectura Calculatoarelor

I Introducere Arhitectura calculatoarelor trateaza comportarea functionala a unui calculator asa cum este vazut acesta de catre programator....

Te-ar putea interesa și

Implementarea Algoritumului Dijkstra pentru Calcularea Drumului Optim Folosind Java

1. Introducere 1.1 Ce este un algoritm?Tipuri de algoritmi folositi pentru calcularea drumului optim Scurt istoric: “Originile teoriei...

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...

Ai nevoie de altceva?