Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Maximalni put, u usmjerenom, aciklicnom grafu

[es] :: Art of Programming :: Maximalni put, u usmjerenom, aciklicnom grafu

[ Pregleda: 2995 | Odgovora: 4 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

NrmMyth
Ivan Maček
Split

Član broj: 63456
Poruke: 849
*.cmu.carnet.hr.

Sajt: www.dump.hr


Profil

icon Maximalni put, u usmjerenom, aciklicnom grafu22.04.2006. u 21:25 - pre 219 meseci
Jutros sam naisao na ovakav problem: "Treba naci najduzi moguci put od A do B u usmjerenom, ne ciklicnom grafu."
Pokusao sam obrnuti Djikstru, ali sam onda shvatio da nece ici.
S Djikstrom mogu stati na konacnoj tocki i biti siguran da je to najkraci put, ali ako napravim Djikstru za maximani put, onda ta teza vise ne stoji, nego treba proci kroz sve cvorove da bi bili sigurni u maximalnost puta, cime dobijemo BFS.

Postoji li kakav brzi algoritam, i jest li se susreli sa ovakvim problemom.
 
Odgovor na temu

RooTeR
Rajko Nenadov
nema ga
Detelinara, NS

Član broj: 2386
Poruke: 385
*.dialup.neobee.net.



Profil

icon Re: Maximalni put, u usmjerenom, aciklicnom grafu22.04.2006. u 21:44 - pre 219 meseci
Neka je maximalna udaljenost od cvora do cvora .
Tada je (od j do i mora postoji diretkna grana)

Da bude malo jasnije :

Code:


dfs(cvor v){
  d[v]=-1;
  za svaki cvor w, takav da postoji grana od w do v 
     ako d[w] nije izracunato, pusti dfs(w)
     d[v]= max(d[v], d[w] + duzina[w][v])
}



[Ovu poruku je menjao RooTeR dana 22.04.2006. u 22:47 GMT+1]
mmmmmm.. aahhhhhh..
e, nije sex nego serem!
 
Odgovor na temu

NrmMyth
Ivan Maček
Split

Član broj: 63456
Poruke: 849
*.cmu.carnet.hr.

Sajt: www.dump.hr


Profil

icon Re: Maximalni put, u usmjerenom, aciklicnom grafu22.04.2006. u 22:43 - pre 219 meseci
Znaci nema sanse da izbjegnem komplentni search? ...
 
Odgovor na temu

RooTeR
Rajko Nenadov
nema ga
Detelinara, NS

Član broj: 2386
Poruke: 385
*.dialup.neobee.net.



Profil

icon Re: Maximalni put, u usmjerenom, aciklicnom grafu22.04.2006. u 23:47 - pre 219 meseci
Pa, ovaj algoritam radi u , jer ti svaki cvor obilazish tacno jednom, tako da to ne bi trebalo da bude problem :)
mmmmmm.. aahhhhhh..
e, nije sex nego serem!
 
Odgovor na temu

NrmMyth
Ivan Maček
Split

Član broj: 63456
Poruke: 849
*.cmu.carnet.hr.

Sajt: www.dump.hr


Profil

icon Re: Maximalni put, u usmjerenom, aciklicnom grafu23.04.2006. u 09:29 - pre 219 meseci
Je... nisam bas razmisljao sinoc.
Top-Bottom DP ...

Hvala, pozdrav. :)
 
Odgovor na temu

[es] :: Art of Programming :: Maximalni put, u usmjerenom, aciklicnom grafu

[ Pregleda: 2995 | Odgovora: 4 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.