最短経路アルゴリズム — ダイクストラは負の重みで壊れる
前の回で「重みが全部同じなら BFS が最短を出す」と分かった。では区間ごとに所要時間が違う路線図では? 10駅の路線図を作り、BFS とダイクストラの答えを同じグラフで並べて、乗り換え1回・40分と乗り換え4回・21分が別物であることを確かめる。次に負の重みを1本だけ入れて、ダイクストラがエラーも出さずに静かに間違えるところを実際に出力する。ベルマン・フォードで正しい答えを出し、負の閉路の検出まで実装して、為替の裁定取引が同じ問題だと確かめる。最後に格子迷路で A* とダイクストラの調べたマス数を数え、最小全域木をクラスカル法とプリム法の両方で解く。