Algorytm znalezienie ścieżki o podanej długości (wadze)

Siemka,
Mój problem wygląda następująco:
Mam graf spójny nieskierowany, gdzie każdy wierzchołek ma liczbę swoją liczbę punktów. Punkty są zbierane za odwiedzenie danego wierzchołka. Muszę znaleźć ścieżkę pomiędzy podanymi dwoma wierzchołkami, przez którą przechodząc "zbiorę" zadaną liczbę punktów. Czy istnieje jakiś algorytm znajdujący rozwiązanie tego problemu, albo chociaż taki, którego modyfikacja dałaby mi rozwiązanie.
W internecie i literaturze znajduje tylko problemy dotyczące najkrótszych/najlżejszych i td ścieżek.

Wygląda, że to może być dowolna droga między dwoma wierzchołkami, to nie pozostaje nic innego, jak zpuścic jakiś BFS odnotować sumę punktów do tego wierzchołka w wektorze i poszukać danej wartości.

Czy możesz dany wierzchołek odwiedzać wielokrotnie? np. 1-2-3 , a szukasz trasy z 1 do 3 o długości 12, np. 1-2-1-2-1-2-3 ?

Brzmi bardzo NP-zupełnie, w szczególności wygląda, jakby się dawało do tego zredukować problem sumy podzbioru…

Nic istotnie sprytniejszego od brute force’a mi do głowy nie przychodzi.

Załóżmy, że masz dojść od A do B z punktami K. Znajdujesz wszystkie wierzchołki mogące wystąpić na ścieżce prostej z A do B (nazwijmy ten podgraf X). Następnie puszczasz DFS z dopuszczalnymi powtórzeniami, ale wykluczając chodzenie po cyklach.
Na oko to i tak będzie wykładnicze, ale przy „normalnych” grafach da się pewnie zoptymalizować przez sortowanie quasi topologiczne.

Możesz też stosować dziel i zwyciężaj, dla każdej wartości k <= K i wierzchołka x z X rozbijasz problem na dojście z A do x z kosztem k + dojście z x do B z kosztem K - k.

yarel napisał(a):

Czy możesz dany wierzchołek odwiedzać wielokrotnie? np. 1-2-3 , a szukasz trasy z 1 do 3 o długości 12, np. 1-2-1-2-1-2-3 ?

Zasadniczo określenie założeń również należy do mnie, ale na początku szukam rozwiązania bardzo ogólnego. Także tak, mogę w szczególności wykonać takie przejście.

Jeśli bez cykli, to masz przykład https://www.geeksforgeeks.org/find-paths-given-source-destination/. Z cyklami to nie wiem czy jest coś lepszego niż bruteforce.