[graph] All-Pairs Shortest-Paths

[ei1333]

[graph] Weighted

Description

• ワーシャルフロイドということです $O(|V|^3)$

File Name

src/graph/all-pairs-shortest-paths/in-weighted-graph.hpp

TODO

• [ ] 実装
• [ ] ドキュメント作成
• [ ] unit-test
• [ ] verify

note

unweighted は #89 と同じノリで bit 並列で $O(\frac {|V|^3} {B})$ にできます

• reference material
  • (url)
• implementation
  • (url)
• 関連 issue / PR
  • #
• verify:
  • (url)

[graph] UnWeighted

Description

https://github.com/luzhiled1333/comp-library/issues/89 と同じノリで bit 並列で $O(\frac {|V|^3} {B})$ にできます

File Name

src/graph/all-pairs-shortest-paths/in-unweighted-graph.hpp

TODO

• [ ] 実装
• [ ] ドキュメント作成
• [ ] unit-test
• [ ] verify

note

• reference material
  • (url)
• implementation
  • (url)
• 関連 issue / PR
  • #
• verify:
  • (url)

[ei1333]

設計をどうしますか

[ei1333]

隣接リストよりも隣接行列で持ちたい気持ちがある

[Luzhiled]

すいません　重みなしAPSPはどんなに適当にやっても $O(NM)$ で解けます

[ei1333]

密なグラフのことを考えていました

[ei1333]

MがN^2

[Luzhiled]

もとのグラフで距離2の頂点間に辺を結んだグラフの隣接行列は行列積から求められて、そこからうまいことパリティを求めることができるのでそれを直径が1になるまで再帰的にやると $O((ここに行列積のオーダー) \log |V|)$ になる、という話は見ました

[Luzhiled]

結局のところ密か密でないかで分ける必要がありそう

[ei1333]

密でない場合はbfsをN回呼び出せば良くないで坂

[ei1333]

それでは行列積の実装を

[Luzhiled]

密でない場合は bfs を N 回呼び出せばいいですが

[ei1333]

なるほど

[Luzhiled]

密である場合だとか密である場合だとか、どう分けるべきなんですかね　判定とかはさすがに諦めてユーザーのみなさんが頑張りましょうですか

[Luzhiled]

こういうことを Discussion でやれ、やられたという感じだ

[ei1333]

密判定士に聞きましょう