最長路問題について

[kotto5]

https://sen-comp.hatenablog.com/entry/2020/01/05/194503

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

とある。ダイクストラについてはこちら
https://products.sint.co.jp/topsic/blog/dijkstras-algorithm

ダイクストラで良さそうではあるが、解決すべき問題は

• データ構造
• そもそもグラフへの理解

あたり。

また、python 等使えばライブラリで実装されているようだが、使用するかどうか
恐らくテスト後の面接でも、テストで解いた問題について説明を求められると思うので、c++ で実装し触ってみる経験を取ろうと思っている
( 今回計算量のオーダーの指定もないので。しかし自分で作るならばエラーが発生するのが面倒なので、テストは入念に作る必要がある )

[kotto5]

https://qiita.com/Morifolium/items/6c8f0a188af2f9620db2

https://take44444.github.io/Algorithm-Book/graph/longest-path/main.html

[kotto5]

#1 (comment)
勘違いした記載をしてしまった。

引用した文は最短経路問題に関しての話
最長路に関しては、グラフの重みを全て-1倍した結果のグラフについて、最短路を求めることと同値であると。
また、その結果のグラフに関しては、負の重みが含まれるので、利用できるのは「ベルマンフォード法」、「ワーシャルフロイド法」のどちらかである

また記事の主張としては、グラフがDAGならトポロジカルソートでDPが使えると言っていたが、今回はDAGではないのでトポロジカルソートは恐らく使えない。

DAG（Directed Acyclic Graph）とは、閉路のない有向グラフ（Directed Graph）のことです。サイクルが存在しないため、ある頂点から同じ頂点に戻ってこれないという特徴があります。

関係ないが、bitDP

[kotto5]

https://qiita.com/wakimiko/items/69b86627bea0e8fe29d5

これの通りに実装すればできそう

[kotto5]

ワーシャルフロイド法で実装できた？が、未テスト。
また、最長の距離は取得できたような気がするが、経路の検出はどうすればいいのかわからない

https://scrapbox.io/hkurokawa-cp/%E6%9C%80%E9%95%B7%E7%B5%8C%E8%B7%AF