Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Arbore de drumuri  (Citit de 2459 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
c_sebi
Client obisnuit
**

Karma: 24
Deconectat Deconectat

Mesaje: 62



Vezi Profilul
« : Aprilie 25, 2008, 21:19:26 »

Cum se construieste graful orientat aciclic al tuturor drumurilor minime?

Multumesc!
Memorat
amadaeus
Client obisnuit
**

Karma: 28
Deconectat Deconectat

Mesaje: 93



Vezi Profilul
« Răspunde #1 : Aprilie 25, 2008, 22:00:16 »

Probabil ca te referi la drumurile minime de sursa unica. Poti adapta algoritmul lui Bellman-Ford: relaxezi de |V| ori toate muchiile si, daca pentru o muchie nu este indeplinita conditia de relaxare, o stergi din graf. Vei ramane cu graful orientat aciclic al tuturor drumurilor minime. Sper sa nu-mi fi scapat ceva..
Memorat

"one of these days I'm going to cut you into little pieces..."
byndrsn
Client obisnuit
**

Karma: 19
Deconectat Deconectat

Mesaje: 72



Vezi Profilul
« Răspunde #2 : Aprilie 25, 2008, 23:05:59 »

Bellman-Ford, Dijkstra, etc. construiesc deja arborele drumurilor minime de la sursa catre orice alt varf. Este suficient sa stochezi predecesorul fiecarui nod.
Memorat
amadaeus
Client obisnuit
**

Karma: 28
Deconectat Deconectat

Mesaje: 93



Vezi Profilul
« Răspunde #3 : Aprilie 25, 2008, 23:31:05 »

Din cate am inteles, Sebi avea nevoie de DAG-ul drumurilor minime, nu numai de arbore.
Memorat

"one of these days I'm going to cut you into little pieces..."
c_sebi
Client obisnuit
**

Karma: 24
Deconectat Deconectat

Mesaje: 62



Vezi Profilul
« Răspunde #4 : Aprilie 26, 2008, 08:49:52 »

Mersi, Lucian.

Asta e solutia de la o problema de la ONI 2005
Citat
Se considera graful format astfel: pentru fiecare camera se considera un nod, iar intre doua camere vecine pe orizontala/verticala (deci doua noduri) o muchie de cost 1 daca nu exista zid intre cele doua camere, respectiv p daca exista zid. Pe acest graf se calculeaza cu algoritmul lui Dijkstra costurile minime de la camera stanga-sus la toate celelalte camere. Apoi se construieste graful orientat aciclic al tuturor drumurilor minime de la camera stanga sus la camera dreapta jos. Pe acest graf aciclic se calculeaza cu o parcurgere drumul dintre cele doua camere care foloseste numar minim de muchii formate din ziduri. Pentru o complexitate mica, algoritmul lui Dijkstra trebuie implementat cu heapuri. Astfel, complexitatea totala e de N^2logN.

Cu Dijkstra cum se poate face?
Memorat
sima_cotizo
Nu mai tace
*****

Karma: 219
Deconectat Deconectat

Mesaje: 596



Vezi Profilul
« Răspunde #5 : Aprilie 26, 2008, 09:18:21 »

Poti sa faci Dijkstra (care iti va scoate drumurile minime de la S la orice nod), iar apoi sa iei fiecare muchie din graf si sa verifici :
Cod:
daca D[x] == D[y]+c atunci
        muchia (x,y) de cost c face parte din arborele drumurilor minime

Apoi, din cate am inteles din citatul tau, ai deja un arbore (graf) pe muchiile caruia daca mergi, ajungi in cost minim de la sursa la orice nod => poti folosi o parcurgere normala O(N+M) ca sa gasesti acea parcurgere cu numar minim de muchii.
Memorat
amadaeus
Client obisnuit
**

Karma: 28
Deconectat Deconectat

Mesaje: 93



Vezi Profilul
« Răspunde #6 : Aprilie 26, 2008, 10:19:56 »

Cu Dijkstra cum se poate face?
Poti determina cu Dijkstra asa cum a spus Cotizo: odata gasita distanta minima pana la fiecare nod, DAG-ul drumurilor minime va fi format din toate muchiile (u,v) pentru care dist[ u ] + cost(u,v) = dist[ v ].

Citat din mesajul lui: Sima Cotizo
Apoi, din cate am inteles din citatul tau, ai deja un arbore (graf) pe muchiile caruia daca mergi, ajungi in cost minim de la sursa la orice nod
Din cate am inteles eu, e un fel de labirint in care sa treci dintr-o celula in alta ai cost 1, si sa spargi un zid ai cost p. Deci nu poti face o parcurgere in graful original pentru a gasi un drum minim. Intr-adevar, dupa ce ai obtinut DAG-ul drumurilor minime, faci o parcurgere si cauti drumul cu cat mai putine muchii de cost p.
Memorat

"one of these days I'm going to cut you into little pieces..."
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines