Czy istnieje algorytm który wyznacza WSZYSTKIE drogi z punktu A do punktu B w grafie skierowanym ? nie mam tutaj na myśli jednej najkrótszej itd. tylko taki który rozwiązuje właśnie taki problem.
0
0
Tak, ale nie ma nazwy bo jest banalny - o ile nie przejmujesz się cyklami.
Ogólna idea jest taka, że wykonujesz rekurencję od A, za każdym razem wywołując z coraz dłuższą listą wierzchołków i gdy dojdziesz do B to wypisujesz listę.
0
Dajmy na to, że mam reprezentacje grafu jako liste sąsiedztwa i czy to o czym mówisz to jest przejrzenie każdego sąsiada z punktu startowego oraz następnych sąsiadów tego nowego itd. aż dojdzie sie do punktu B ? tylko że takie coś będzie mieć nieakceptowalną złożność...
0
Tyle, że w grafie z N wierzchołkami pesymistycznie może być co najmniej 2N ścieżek pomiędzy punktem A i B, więc jeśli byś chciał je wszystkie wypisać to złożoność wyniesie O(2N * N) (bo wypisanie jednej ścieżki to O(N))
Pewną optymalizacją może być wstępne przejście grafu z odwróconymi krawędziami i sprawdzenie dzięki temu z których wierzchołków da się dojść do B. Potem na oryginalnym grafie odpalamy wspomnianą rekurencję i jeśli dotrzemy do wierzchołka z którego nie da się dostać do B to natychmiast wracamy.
0
Złożoność nie powinna przekroczyć n^3 a chyba przekroczy..
0
W załączniku podałem przykładowy "graf" - tzn jeśli założymy, że każdy róg to wierzchołek i krawędzie biegną tylko w prawo to jest to graf skierowany. Jeśli N to liczba rombów wyznaczonych przez taki graf to ilość ścieżek pomiędzy A i B to 2N, a więc N3 nie da się uzyskać.
0
Jeżeli w grafie będą trzy takie węzły K,L,M że są drogi K->L oraz L->M oraz M->K to masz natychmiast nieskończoną ilość dróg.
Oczywiście może takich węzłów być dwa K->L oraz L->K.
Lub cztery K->L L->M M->N N->K
Lub ... dalej sam dopiszesz.
Więc algorytm o jaki prosisz nie może istnieć.
0
Musi się dać... to jak rozwiązać problem maksymalnej przepustowości w przyzwoitym czasie ? Dla takiego problemu konieczne jest wyznaczenie wszystkich dróg z A do B oraz obliczenie przepustowości dla każdej z tych dróg oraz wybranie najmniejszej lub największej z nich.
0
A jak definiujesz maksymalną przepustowość?
Chodzi mi o dwa przykłady:
A->(3)->B A->(5)->B - dwie przepustowości równolegle 3 i 5
oraz:
A->(3)->C C->(5)->B - dwie przepustowości szerewgowo 3 i 5
jaka jest przepustowość w pierwszym przypadku a jaka w drugim?
Rozumiem że w tablice sąsiedztw masz tą przepustowość wpisaną?
0
Wejście, jest takie, że posiadam tablice sąsiedztwa, graf może mieć cykle tzn. mając A, B, C będę mógł przejśc z A->B->C itd. chodzi o to, że krawędzie maja pewną wartość(przepustowosc) i musze wyznaczyc maksymalna przepustowosc dla danych 2 punktow. docelowo dla kazdej pary