最長路問題について

kotto5 commented 8 months ago

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

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

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

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

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

あたり。

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

kotto5 commented 8 months ago

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

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

kotto5 commented 8 months ago

https://github.com/kotto5/dreamarts_test/issues/1#issue-2061446809 勘違いした記載をしてしまった。

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

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

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

関係ないが、bitDP

kotto5 commented 8 months ago

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

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

kotto5 commented 8 months ago

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

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

kotto5 / longest_path_problem

最長路問題について #1