単一始点最長路

グラフに，始点から到達可能な重みの合計が正の閉路がある場合，その閉路を周ることでいくらでも路長を大きくすることができるため，解は存在しない．

上の条件に当てはまっていない場合，重みの正負を逆転させることで，最短経路問題に変換することができるため，Bellman Ford法(\(O(|V||E|)\))等で解けば良い．自明だが，元のグラフの辺の重みが全て負であった場合は，より高速なDijkstra法(\(O(|E| \log |V|)\))で解くことができる．

また，元のグラフに正の辺があったとしても，グラフが有向非巡回グラフ(DAG)である場合は，ノードをトポロジカルソートをして，順にDPで始点からの最長路求めていく(\(O(|V| + |E|)\))ことができる．

グラフに，始点から到達可能な重みの合計が正の閉路がある場合で，解を求められるように，それぞれのノードは\(1\)回しか通れないというような制約が与えられることがある．これは，巡回セールスマン問題とほぼ同じ問題であるため，NP困難な問題である．bitDPにより\(O(|V|^22^{|V|})\)で解ける．