|
Titlul: Arbore de drumuri Scris de: Sebastian Crisan din Aprilie 25, 2008, 21:19:26 Cum se construieste graful orientat aciclic al tuturor drumurilor minime?
Multumesc! Titlul: Răspuns: Arbore de drumuri Scris de: Lucian Boca din 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..
Titlul: Răspuns: Arbore de drumuri Scris de: Alina Ene din 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.
Titlul: Răspuns: Arbore de drumuri Scris de: Lucian Boca din Aprilie 25, 2008, 23:31:05 Din cate am inteles, Sebi avea nevoie de DAG-ul drumurilor minime, nu numai de arbore.
Titlul: Răspuns: Arbore de drumuri Scris de: Sebastian Crisan din 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? Titlul: Răspuns: Arbore de drumuri Scris de: Sima Cotizo din 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 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. Titlul: Răspuns: Arbore de drumuri Scris de: Lucian Boca din 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. |