다른 모든 노드에 도달 할 수있는 특수 루트 노드가있는 유향 그래프가 있습니다.유향 그래프에서 노드에서 루트까지 경로를 찾는 수행 그래프 알고리즘
부여 노드에서 루트까지 모든 pathes를 찾는 임의의 알고리즘을 쉽게 찾을 수 있습니다 (예 : solution (DFS) using LinkedHashSets).
음,이 알고리즘은 작은 그래프에서는 잘 작동하지만 큰 그래프에서는 적당한 시간 내에 끝나지 않습니다.
예제 그래프에는 노드가 129 개 있고 가장자리가 200 개 있습니다. 내 눈에 하지이며 매우 거대한 그래프 ...
누군가가 나에게 효율적으로이 문제를 해결하는 방법에 대한 힌트를 줄 수 있습니까?
아마도 내 그래프의 다른 속성을 사용할 수 있습니다. 그들은 모두는 다음과 같습니다
자에게이 지정된 시작 노드는 정말 한 - 당신은 훨씬 더 많은 수 없습니다 왜냐하면 출력 크기 자체가 크기 때문입니다. 경로의 수는 노드의 수가 기하 급수적이다,이 간단한 예제를 보라 : C로 이어지는 그래프에서 "만"이 없음 사소한 경로가
V = {a, b, c}, E = {(a,b), (a,c), (b,c)}
이 아주 간단 보인다. a-> c, a-> b-> c. 당신이 너무 나쁜 아직, d->a->c, d->a->b->c, 3 개 경로가 새로운 루트에서 c에 이르는 d->b->c을 가지고 있지만 것 -
지금은 가장자리 (D, A), (d는, B)와 노드 d을 추가하는 것을 고려 에 (e,d),(e,a)을 추가하면 어떤 일이 발생하는지 알아 보려면 e->d (경로 위에 3 개)으로 시작하는 경로와 "e-> a"(2 개 경로)로 시작하는 경로의 "패밀리"중 하나를 얻을 수 있습니다. 총 5 개 경로. 이 과정을 반복하면 5 개의 경로가있는 하나의 패밀리와 다른 3 개의 패밀리가 생성됩니다. 아마도 k 번 과정을 반복하면 but the fibonacci number is very, very big for inputs such as 100 (~ 354 * 10^20)이라는 경로와 #fibo(k) 개의 다른 경로가 생겨 빠르게 성장한다는 것을 이해하게 될 것입니다.
이렇게하면 그래프의 모든 경로를 찾는 것이 나무 같은 일부 "쉬운"그래프를 제외하고 비효율적입니다.
TL; DR : 지수 대상 노드에 이르는 경로의 수, 그들 모두가 기하 급수적으로 시간이 걸립니다 찾는이 있습니다
. DFS는이 문제에 대한 견고한 솔루션입니다.
dijsktra alghoritem을 사용해 보셨나요? – Jure
DFS는 O (n)입니다. 그보다 더 잘할 수 있다는 것은 확실하지 않습니다 ... –
dfs보다 훨씬 좋은 것을 찾을 수는 없을 것 같지만, 여기를보십시오 http://stackoverflow.com/questions/26857842/find -shortest-path/26858645 # 26858645 – Lrrr