3개의 댓글이 있습니다.
-
-
Taeyoon_Lee -
싸이클이 없으므로, 특별한 알고리즘이 필요 없을 것 같고, 위상정렬 하듯이 in-degree가 0인 버텍스부터 처리해나가면 될 것 같습니다.
12년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
mujugi
어떤 그래프가 있습니다
방향그래프이고 사이클은 없습니다
명확하게 edge의 cost는 부여되지 않았으며
vertex에만 특정한 확률값이 부여되어있습니다.
예를들어 다음과 같습니다
vertex
a 0.1
b 0.4
c 0.3
d 0.2
e 0.1
그래프를 인접리스트형태로 표현하면 다음과 같습니다
a : [b, c]
b : [d, e]
c : [d, e]
소스는 a 하나고
말단은 d나 e가 됩니다
edge의 거리는
이때 a->e 까지
혹은 a->d 까지의 최대 곱 경로를 알고 싶습니다
ex> a-d 의까지의 조합
a -> b -> d
0.1 * 0.4 * 0.2
a -> c -> d
0.1 * 0.3 * 0.2
요기에서는 a -> b -> d가 최장 곱경로인것을 알 수 있습니다.
처음엔 다익스트라로 (1-vertex) 의 값이 최소가 되는 경로를 찾아봤더니 옵티멀 보장이 되지 않더군여
(-vertex) 하면 음수라서 안되고
벨만포드로 (-vertex)를 해볼까 생각중입니다.
어떤 알고리즘을 쓰는 것이 좋을까요?
p.s 소스부터 말단까지의 거리보다 소스부터 말단까지의 trace가 중요합니다
(다익스트라에서는 trace를 구하기 쉬운데 벨만포드는 어떤가요?)
감사합니다
12년 전