競技プログラミングで使う有名グラフアルゴリズムまとめ

0. はじめに AtCoderなどでは、グラフを扱った問題が多く出るが、その度に一から実装していると時間が掛かりすぎてしまうため、有名なものをあらかじめ持っておく必要がありそう。そこで、Pythonを用いて、ダイクストラ法、ベルマンフォード法、プリム法、クラスカル法、ワーシャルフロイド法を実装した。 コメント、意見等ある方は是非! お待ちしてます! 1. ダイクストラ法 1.1. ダイクストラ法(defaultdictで実装) defaultdictで実装すると、リストで実装するよりも、ノード数$N$が大きい際には高速に動作する。ただし、経路復元の関数は、うまく書けなかった......。 (2019/7/6 追記)結局できました。1.1.1. を参照してください。 import collections import heapq class Dijkstra: def __init__(se

[taguch1]

後で読む(ような気がする)

[bull2]

あとでやれるか？

[hara_boon]

競プロやってみたい気持ちはある

[aceraceae]

グラフ理論は学生時代に習ったきりだからなあ。教科書はとってあるけど。ダイクストラ法とか懐かしい。

[uunfo]

ゴルフだと思って読んでみて意味が分からないと思ったらグラフだった

[goto_miiraku]

グラフは応用範囲が広いので勉強になります

[ssids]

忘れたときのためにいつでも本棚にヤドカリ本は置いておきたい

[kuro_pp]

もう10年くらい離れてるから付いていけるかどうか……

[yarumato]

“AtCoderでグラフを扱った問題が多く出る。有名なアルゴリズムをPythonで実装：ダイクストラ法、ベルマンフォード法、プリム法、クラスカル法、ワーシャルフロイド法”

[morita_non]

後で読む

[shoh8]

短期決戦の時に使える道具は多いほうがいい

[deokisikun]

グラフアルゴリズムという概念すら初耳だった