[Algorymika] Najkrótsza scieżka w grafie


(Cinek Cnx) #1

Z problemem zmagam się już dłuższy czas. Nie jest tak trywialny jak wydaje się na pierwszy rzut oka.

Musimy znaleźć dystans najkrótszej ścieżki w grafie ważonym nieskierowanym z wierzchołka A do wierzchołka B. Tak wiem, wiele osób w tym momencie myśli "co za ciemniak" bo przecież są algorytmy takie jak Dijkstra, A*, Bellman-Ford, BFS, DFS itp. których do tego powszechnie używamy. Mówiąc szczerze znam je wszystkie mniej lub bardziej (ten temat nie jest mi obcy).

Problem leży jak to zwykle bywa w algorytmice w limicie złożoności czasowej projektowanego algorytmu który wynosi:

O(e+v)

v - ilość wierzchołków

e - ilość krawędzi grafu

Taki jest problem z którym się zmagam i nad tym kto go układał nie chcę dyskutować.

Prośba o pomoc do forumowiczów: macie jakieś pomysły na algorytm pracujący z taką złożonością , pozwalający znaleźć dystans najkrótszej możliwej ścieżki z wierzchołka początkowego do końcowego?

A może ktoś uważa, że taki algorytm nie istnieje? (Czasami sam nad tym się zastanawiam bo gdyby istniał algorytm o złożoności O(e+v) to po co komu Dijkstra o złożoności O(e log v) w implementacji bodajże kopcowej?)


([alex]) #2

"pozwalający znaleźć tylko dystans (na podstawie wartości wag znalezionej najkrótszej ścieżki)"

Normalnie sumujesz przechodzone krawędzi, to wszystko.


(Cinek Cnx) #3

może źle się wyraziłem mówiąc że na podstawie wartości wag najkrótszej ścieżki. Chodziło mi raczej o znalezienie ścieżki, której suma wag będzie najmniejsza i podanie tej sumy (przysłowiowa "najkrótsza trasa" - najmniejszy dystans).


(Marcin 110) #4

Algorytm Dijkstry na kopcach Fibonacciego działa w czasie O(v*logv + e), a to dosyć blisko. Może ten graf jest jakiś nietypowy, np. nie zawiera cykli?


(Cinek Cnx) #5

Implementacja na kopcach Fibonacciego jest bardzo skomplikowana a realny zysk jeśli chodzi o złożoność asymptotyczną nie jest taki duży w stosunku do implementacji na zwykłych kopcach binarnych. Coraz bardziej utwierdzam się w przekonaniu, że złożoność O(v+e) jest nieosiągalna. Przeczytałem całe google w tej sprawie :? Żaden algorytm mi nie pasuje. Najbliższy wydaje się BFS ale on daje ciała w grafach ważonych.