Srodne teme

04.06.2002. Najkraci put izmedju dva cvora u grafu
25.01.2004. Ge Force 4mx umesto 2mx
26.02.2004. Koji maximalni kapacitet diska vidi Windows ME??
04.03.2005. Vise informacija o satelitskoj televizij na PC-u?!
24.03.2005. MaxClique problem
15.06.2005. Cepanje najbolje?
13.09.2005. Link sa 2 Cisco AP1200
14.12.2005. Download-Max. velicina
11.12.2005. pomoc oko bittorrenta
09.04.2006. Konekcija opada, signal nikako nije dobar...

Navigacija

Brisanje liste

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

Maximalni put, u usmjerenom, aciklicnom grafu

[es] :: Art of Programming :: Maximalni put, u usmjerenom, aciklicnom grafu	[ Pregleda: 840 \| Odgovora: 4 ]	Postavi temu Odgovori

Autor

NrmMyth
Split, Kaštela

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

Profil

Maximalni put, u usmjerenom, aciklicnom grafu

^{22.04.2006. u 21:25}

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.

http://www.last.fm/user/NrmMyth/

^{22.04.2006. u 21:25}

RooTeR
Rajko Nenadov
Detelinara, NS

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

Profil

Re: Maximalni put, u usmjerenom, aciklicnom grafu

^{22.04.2006. u 21:44}

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!

^{22.04.2006. u 21:44}

NrmMyth
Split, Kaštela

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

Profil