数学/競プロメモ

拡張ダイクストラ(Dijkstra)法

拡張Dijkstra法

グラフを拡張してDijkstra法を適応すること

「拡張ダイクストラ法」っていう言い方は、ダイクストラ法自体が拡張されている印象を受けるのでちょっとどうかと思う。「拡張グラフでのダイクストラ法」の方が適切では（まあこれを省略したのが「拡張ダイクストラ」なんだろうけど）。
— えびま (@evima0) 2013年5月15日

頂点を拡張させる方法と辺を拡張させる方法がある。

問題