[ NrmMyth @ 22.04.2006. 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.
[ RooTeR @ 22.04.2006. 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]
[ NrmMyth @ 22.04.2006. 22:43 ] @
Znaci nema sanse da izbjegnem komplentni search? ...
[ RooTeR @ 22.04.2006. 23:47 ] @
Pa, ovaj algoritam radi u , jer ti svaki cvor obilazish tacno jednom, tako da to ne bi trebalo da bude problem :)
[ NrmMyth @ 23.04.2006. 09:29 ] @
Je... nisam bas razmisljao sinoc.
Top-Bottom DP ...

Hvala, pozdrav. :)