有向グラフの最短路と最長路問題 - Senの競技プログラミング備忘録

有向グラフの最短距離は、

負の辺が存在しないのならば、「ダイクストラ法」
負の辺が存在するならば、「ベルマンフォード法」、「ワーシャルフロイド法」

がこれを求めるアルゴリズムとして知られていて、そのうち、「ダイクストラ法」がこの3つの中で唯一E = 100000, V = 100000オーダーでも制限時間内でACできるものである。

ここで、有向グラフの最長距離について、考えてみる。

実は、最長距離は最短距離に次のように言い換えることができる。
「辺のコストを-1倍して、最短距離問題を求める」

しかし、ほとんどの場合、元のグラフの辺のコストは正なので、この操作を適用すると、負のコストを持った辺を持つグラフの最短路となり、適用できるアルゴリズムは、ベルマンフォード法のみである。
また、この言い換えをせずに、大きい順から出すpriority_queueを用意して、最長距離を求めるダイクストラ法をする場合でも、次のようなケースの場合、
f:id:Sen_comp:20200105164417j:plain
最長路だと思いその先々まで更新していたが、実は最長路ではなかったので、先々までの更新をやり直す
ということが最悪O(N)回起きうるため、全体的にO(N^2 log N)となるとわかる。