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?)