Najdłuższa ścieżka w grafie skierowanym.

Witam,

Mamy graf skierowany z wagami krawędzi. Używam listy sąsiedztwa. Na wejściu podajemy ilość wierzchołków oraz wierzchołek startowy, następnie ilość sąsiadów dla każdego węzła oraz wagi łączących ich krawędzi.

Problem:
Znaleźć najdłuższą względem wag krawędzi możliwą ścieżkę.

Obecnie wykorzystuję BFS, ale niestety nie przechodzi wszystkich testów. Czy mogę prosić o pomoc lub jakieś propozycje? Czy BFS będzie tu dobrym rozwiązaniem? Myślałem również o wykorzystaniu Dijkstry. Byłbym bardzo wdzięczny :)

Oto przykładowy graf:

Przez "najdłuższa scieżka" rozumiesz "najdłuższa w sensie ilości wierzchołków/krawędzi"? Czy może "najdłuższa w sensie sumy wag krawędzi leżących na scieżce"?

Czy graf jest acykliczny? jeśli tak to najpierw posortuj topologicznie i chyba wystarczy potem przelecieć po wierzchołkach w porządku topologicznym (albo na odwrót, nie pamiętam) zaczynając od startowego i sprawdzać czy można przedłużyć ścieżkę, chyba powinno zadziałać.
jeżeli graf ma cykle to:
Dijkstra jeżeli masz pewność że nie ma dodatnich cykli (wtedy ścieżka byłaby nieskończona) przy czym poczatkowe odległości od źródła ustawić na -INF
bellman-ford jak nie masz pewności czy sa dodatnie cykle

Jeśli wagi krawędzi są dodatnie, to odwróć te wagi (na ujemne) i odpal Dijkstre.