Witam :)
Zna ktoś algorytm, który wyszuka w nieskierowanym grafie ważonym o wagach nieujemnych najdłuższą ścieżkę między dwoma wierzchołkami odwiedzając każdy wierzchołek conajwyżej raz ?? Najlepiej, gdyby była to przeróbka algorytmu Forda-Bellmana, ale nic się nie stanie jeżeli nie będzie. Próbowałem z ujemnymi wagami i odwrotnymi warunkami, ale i tak zapętla się, przez odwiedzanie ciągle tego samego wierzchołka.
0
0
Drobna zmiana pytania :) Chyba, że odpowiedź na tamte jest łatwiejsza. Mogę zmienić zadanie, by wystarczyło znaleźć najdłuższą drogę w grafie ważonym o wagach nieujemnych nieskierowanym taką, by odwiedzić jak najwięcej krawędzi w drodze do danego punktu z danego. Każdą krawędź można odwiedzić tylko raz.
0
Pierwszy problem to jest wariacja na temat problemu komiwojażera, czyli problem NP-zupełny.
Drugi problem to zwykłe szukanie drogi Eulera w grafie (w tym przypadku warto dodać krawędź z wierzchołka końcowego do tego poczatkowego i szukać cyklu Eulera, a potem tą krawędź usunąć), które jest dość trywialne.