1. 負辺があるグラフでダイクストラ法をすると時間がかかる

• 負辺を含むグラフでダイクストラ法をやった例

  ダイクストラ法2.mp4

  下下下ルートから上上上ルートまで8通り全部試してしまっている。三角の数が増えると指数関数的に計算時間が増加する。

2. 頂点倍化

tbw

参考: 今だからこそ学ぶプログラミングとアルゴリズム - YouTube （ちょくだいさんの動画）

著作権的に公開できないパート

他の人の著作物を使っていて公開できない部分は別ページに切り出す

ダイクストラ法 (著作権的に問題あり)

メモ

• 普通のダイクストラ法はパス上の辺重みの総和を最小にするものである。一方、パス上の辺重みの最大を最小化したり、パス上の辺重みの最小を最大化したりというのもダイクストラ法でできる？（要確認）
  • 参考: JOI2012 本選 問題5 JOI 国のお祭り事情 解説