Tema
Boje
Pismo
Registracija

Novo

Forum kao aplikacija na telefonu

Dodajte forum na početni ekran i koristite ga kao aplikaciju, sa menijem na dnu ekrana.

Kako se dodaje

Maximalni put, u usmjerenom, aciklicnom grafu

Odgovori Nova tema
Štampanje RSS teme Kopiraj vezu do teme Podeli na Facebook-u Podeli na X-u (Twitter) Idi na poslednju poruku
  • 4 odgovora
  • 4.039 pregleda

Najnovija ↓

Maximalni put, u usmjerenom, aciklicnom grafu 22.04.2006. u 22:25 · pre 249 meseci #1
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.
Re: Maximalni put, u usmjerenom, aciklicnom grafu 22.04.2006. u 22:44 · pre 249 meseci
izmenjeno 1 put, poslednji put RooTeR 22.04.2006. u 22:47
Izmene poruke
  1. RooTeR22.04.2006. u 22:47zapis iz teksta poruke
#2
Neka je d_i maximalna udaljenost od cvora A do cvora i .
Tada je d_i = Max ( d_j + duzina_{j,i} ) (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])
}

Potpis
mmmmmm.. aahhhhhh..
e, nije sex nego serem!
Re: Maximalni put, u usmjerenom, aciklicnom grafu 23.04.2006. u 00:47 · pre 249 meseci #4
Pa, ovaj algoritam radi u O(n) , jer ti svaki cvor obilazish tacno jednom, tako da to ne bi trebalo da bude problem :)
Potpis
mmmmmm.. aahhhhhh..
e, nije sex nego serem!
Odgovori
Prijavite se da biste odgovorili u ovoj temi.PrijavaRegistracija

Premeštanje teme