[PHP] Zliczanie dróg w tablicy Opcje

[suxone]

Siedzę już sporo czasu nad tym i nie mogę wymyślić. Problem jest taki, że mam tablicę i chce policzyć drogi zależności pomiędzy wierzchołkami. Dla przykładu:

Kod

X A B C D
A 0 1 1 1
B 0 0 1 1
C 0 0 0 1
D 0 0 0 0

Jadąc od ostatniej kolumny i ostatniego wiersza napotykamy się przy 1 połączone D-C, więc kolejnym krokiem jest udanie się do kolumny C, gdzie stoi wartość przy A - droga dla tego przykładu zatem wynosi D-C-A, trzeba zrobić to dla wszystkich elementów z połączonych razem występujących w kolumnie D. Niby wszystko jest ok, tylko, że w kolumnie C nastepuje rozwidlenie na dwie drogi D-C-B i D-C-A, pomysłu nie mam .

Więc występują tu 4 drogi, D-C-A, D-C-B-A, D-B-A i D-A. W jaki sposób można to zapisać kodem (policzyć)?