負の重みを含んだ最長経路の求め方

皆様のアイデアを頂戴したいです。

仕事上の目的で、下のような有向グラフの最長経路を求めたい
と考えております。①から⑤までです。

実際のグラフはもっと複雑です。ですので総当たりは難しいです。

最初ダイクストラ法を用いようと考えましたが
①ダイクストラ法は最小経路を求めるので、そのままでは最長経路
が求められない。
②負の重みがある。
ため断念しました。

上手くこの問題をダイクストラ法で解く方法、あるいはダイクストラ法
に限らず解く方法はないでしょうか。