Biorąc pod uwagę ukierunkowany nieważony wykres acyliczny, staram się zaadaptować algorytm Floyd-Warshall, aby policzyć liczbę ścieżek między 2 wierzchołkami. Mój kod wygląda obecnie tak:

dla wszystkich k w 1 do n dla wszystkich i w 1 do n dla wszystkich j w 1 do n Aij = Aij + (Aik * Akij).

Dlatego zamiast sprawdzać i zamieniać odległość minimalną, wykonuję następujące czynności:

Liczba ścieżek między (i,j) bezk + (Liczba ścieżek zi dok * Liczba ścieżek zk * j )

Moja ostatnia tablica powinna mieć liczbę ścieżek między dowolnymi 2 wierzchołkami.

Nie jestem w stanie udowodnić, że nie daje mi to liczby prostych ścieżek między 2 wierzchołkami, ale nie ma żadnych sugestii, aby użyć tego podejścia gdzie indziej.

Czy ktoś może podać przykład, w którym to się nie powiedzie?

PS: To nie jest moja praca domowa, ale tylko ćwiczenie programistyczne, które podjąłem.