Witam. Piszę system genealogiczny pod moje drzewo o ok. 42000 osób i zastanawiam się nad algorytmem znajdowania najkrótszej ścieżki łączącej dwie dowolne osoby na drzewie. Nie chodzi tu tylko o pokrewieństwa, ale też o osoby spowinowacone itp.

Zastanawiam się jak podejść do tego problemu. Jakiego algorytmu użyć? Myślałem o algorytmie Dijkstry, ale ten polega na znalezieniu najkrótszej ścieżki z wielu możliwych, podczas gdy tu będzie zazwyczaj jedna. Myślałem o implementacji którejś z metod przeszukiwania grafu (BFS i DFS) ale wszystko sprowadza się do sprawdzenia po kolei każdej możliwej ścieżki w drzewie.

Czy znacie jakiś ciekawy algorytm który nie wykorzystywałby metody siłowej?

Pozdrawiam

Może to Ci pomoże

Przenoszę na PHP.

Hmm, czyli jednak Dijkstra. Dzięki