Znajdowanie połączeń/sąsiadów

Witajcie,

Mam na starcie taką tablicę z portami lotniczymi:

itd.

Table pokazuje możliwe połączenia między miastami. Potrzebuję algorytmu, który znajdzie wszystkie możliwe połączenia z jednego portu do drugiego łączenie z przesiadkami. Nie chcę ograniczać liczby przesiadek, lecz zrobić to jakąś funkcją rekurencyjną, która by pokazywała wszystkie możliwe opcje. Zakładam, że nie ma sensu wracać do miasta w którym się już było.

Mniej więcej widzę jak to powinno wyglądać, ale nie mogę napisać działającej funkcji rekurencyjnej która by znajdywała wszystkie drogi, usuwała po drodze miejsca już odwiedzone itp. Czy ktoś mógłby poratować i napisać jak to powinno wyglądać w pseudo-kodzie, pascalu, c++? Ewentualnie konkretny przepis jak to zaprogramować.

Połączenia zapisujesz sobie w tabeli, jak dla grafów:

  1 2 3 4
1 0 1 1 0
2 0 0 0 1
3 1 0 0 0
4 1 0 0 1

Wybierasz sobie jakiś początek i dla małych grafów lecisz algorytmem zachłannym. W sumie to chyba wszystkie tego typu algorytmy bez heurystyki są zachłanne. Ale heurystyka oznacza, że nie będziesz miał sprawdzonego wszystkiego.

Rekurencyjnie lecisz po wszystkich sąsiadach wychodzących ze stacji początkowej. Gdy dochodzisz do stacji końcowej to zapisujesz gdzieś tą ścieżke, ale lecisz dalej. Jak znajdujesz kolejną to sprawdzasz, czy ją masz, jak nie masz to zapisujesz itd.

Dla dużych grafów to już się tak nie da, bo za dużo obliczeń. Wtedy algorytmy genetyczne Ci zostają raczej tylko.

Opolski Portal Programistyczny
http://programowanie.opole.pl

Wszystkie możliwe opcje:
http://www.ideone.com/pBlW1
:)

Generalnie najkrótszą ścieżkę między dwoma wierzchołkami liczy algorytm Dijkstry, ale ty chcesz wszystkie. Może jednak nie chcesz wszystkich tylko np wszystkie oddalone od optymalnego nie więcej niż X jednostek czasu - wtedy mógłbyś użyć zmodyfikowanego Dijkstry.