[Algorytmy] Graf skierowany - wszystkie drogi

[matinf]

Witam,
Mam graf skierowany, acykliczny i planarny. W jaki sposób mogę policzyć wszystkie drogi z wierzchołka \(\displaystyle{ s}\) do wierzchołka \(\displaystyle{ v}\)? Nic mi do głowy nie przychodzi.

[miodzio1988]

Ogólnie się pytasz czy dla jakiegoś konkretnego grafu?

[matinf]

graf jest w pewnym sensie konkretny, sam rzuć okiem:

[miodzio1988]

No to położenie tego drugiego wierzchołka decyduje o tym ile tych dróg będziemy mieli

[matinf]

Nie rozumiem. Wierzchołek docelowy będzie w innym miejscu niż \(\displaystyle{ S}\) (start). Będzie gdzieś indziej, potrzebuję teraz wiedzieć ile jest różnych dróg z \(\displaystyle{ S}\) do celu. Mogą drogi mieć powtórzone krawędzie, byle nie było idealnie te same. Tzn. na ile sposobów mogę tak przejść.

[miodzio1988]

Nie rozumiesz, że położenie celu wpływa na to ile będzie takich dróg?

[matinf]

Nie rozumiesz, że położenie celu wpływa na to ile będzie takich dróg?

Rozumiem - nie ma nic w tym dziwnego.
Sugerujesz zatem abym znalazł zależność?

[miodzio1988]

Nie. Sugeruje, żeby obrać sobie punkt końcowy najpierw

[matinf]

Punkt końcowy będzie podany, któryś z innych niż start

[Ein]

Zaczynasz od danego wierzchołka startowego i idziesz do jego wszystkich sąsiadów (wg skierowania krawędzi), od nich do następnych itd., za każdym razem przekazując powiększoną o jeden wierzchołek ścieżkę i sprawdzając, czy już nie byłeś w tym wierzchołku w tej ścieżce (żeby się nie zapętlać). Jeżeli ścieżka kończy się danym wierzchołkiem końcowym, to ją zapamiętujesz/drukujesz/co tam potrzebujesz.

Ot, taki szybki zarys algorytmu.

[ksisquare]

Na początek wszędzie zero, a jeden w S
A teraz od dołu do góry, od lewej do prawej wstawiamy sumę wierzchołków które prowadzą do bieżącego.

Kod: Zaznacz cały

 0 --> 2 --> 7
       ^     ^
       |     |
 1 --> 2 --> 5
 ^     ^     ^
 |     |     |
 1 --> 1     3
 ^           ^
 |           |
 1 --> 2 --> 3
 ^     ^     ^
 |     |     |
 1 --> 1 --> 1

[matinf]

Ok, pytanie czy sprawa bardzo się skomplikuje gdy krawędzie będę dwukierunkowe, ale tylko te które prowadzą w przód - będą również prowadziły w tył.

[Ein]

W moim algorytmie się nic nie zmieni. Sprawdzanie kierunków krawędzi można całkowicie pominąć i po prostu przechodzić do wszystkich sąsiadów.

[Zordon]

programowanie dynamiczne, klasyczny przykład