BFS czy Dijkstra?

Mamy graf nieskierowany ważony, chcemy znaleźć najkrótszą sciężke (o najmniejszej sumie wag) z pojedynczego zródła do pojedynczego celu. Od tego jest algorytm Dijkstry, A*, i jeszcze kilka innych, ale czy można zrobić to bfs-em?
Standardowo, puszczamy BFS ze zródła.
Jeśli znajdziemy cel, wywołania rekurencyjne się wracają, wracamy zatem naszą scieżką do zródła i przy okazji liczymy sume wag na scieżce.
W zródle po prostu bierzemy minimum z otrzymanych wartości.

Oczywiście - wymaga to dodatkowej pamięci, bo trzeba pamiętac scieżkę wracając się - może być ona rozwiązaniem, więc chcemy ją znać.
Mam wrażenie, że to czasowo jest w O(|V| + |E|).
To jednak niemożliwe, sam w to nie wierze ;p Gdzie zatem jest błąd w moim rozumowaniu?

Jak graf jest ważony to odpada. Bo może tak być że co prawda dojdziesz do wierzchołka docelowego ale niekoniecznie trasą optymalną. Prosty kontrprzykład:
Graf to trójkąt A,B,C. Szukasz ścieżki między A i C. Bezpośrednia krawędź ma wagę 100, a krawędzie AB i BC mają wagi 1. BFSem znajdziesz jako rozwiązanie AC, któremu do optymalności trochę brakuje.

BFSa można stosować do tego problemu ale tylko dla grafów nie-ważonych.

Chodziło raczej o BFSa takiego, który idzie w wierzchołki czarne. Inaczej mówiąc - takim BFS znajdujemy wszystkie możliwe drogi pomiędzy naszą parą wierzchołków i wybieramy najkorzystniejszą.

o_O to sie wtedy nie nazywa BFS i z liczeniem złożoności trochę ci nie siadło :D Bo dla grafu pełnego wszystkich potencjalnych ścieżek będzie wykładniczo dużo ;]

I mam rozumieć, że nie ma sensu próbować to optymalizować, tak? Bo moglibyśmy chociażby zrobić ten "bfs" z odcinaniem, tj kiedy znaleźliśmy jakąś droge i jest ona lepsza od aktualnie analizowanej, to nie ma sensu.

Nie no jasne że możesz sobie optymalizować ale nie zmienia to wcale średniej złożoności obliczeniowej, bo zawsze można przygotować pesymistyczny zestaw danych na ktorym to twoje odcinanie guzik da. Po to właśnie ludzie wymyślili lepsze algorytmy ;) Bo wiesz, dla posortowanego ciągu bubble sort będzie szybszy od merge sorta, ale to wcale nie jest argument za tym żeby z niego faktycznie korzystać ;)

Jaka jest zatem złożoność takiego rozwiązania i jak ją wyznaczyć?

To akurat dość proste. W grafie pełnym krawędzi jest E = V². A ty chcesz sprawdzić wszystkie możliwe podzbiory ze zbioru krawędzi. Zauważ że nie ma znaczenia że interesują cię tylko te pomiędzy wierzchołkiem A i B, bo możemy odrzucić te wierzchołki a następnie dla każdego potencjalnego podzbioru dodawać krawędzie A-podciąg-B skoro graf jest potencjalnie pełny. Dla odpowiednio dużego V możemy założyć że V-2 ~=V więc nie wpływa to na złożoność problemu.
Liczba podzbiorów zbioru N elementowego to oczywiście 2^N więc w naszym przypadku potencjalnych rozwiązań jest 2^E = 2^V*V
Mówie o podzbiorach bo graf jest nieskierowany. Gdyby był skierowany to oczywiście kolejność krawędzi miałaby znaczenie i każde z naszych potencjalnych rozwiązań trzeba by jeszcze permutować...

Dzięki wielkie, już rozumiem.