Hmm...6

バグ発見！昨日の実装メモの中で

これを細分化して、自分のプログラム上でどう表現されているか確認すると

1. 訪れていない点の集合=先行点を納める配列中で、内容がNILの点
2. 既に木に加わっている点の集合=先行点を納める配列中で、内容がNILではない点
3. 交差する辺=既に木に加わっている点の集合からまだ訪れていない点への集合のパスを持っている点。<-これができてないぽいので、修正したら、サンプルインプットは通った。

と書いた。しかし、一度別の点からの先行点になっているからといって、その時に求めた解(始点からの距離)が最短であるという保証はない。よって、1.によってアルゴリズムが破綻してしまっている。具体的には、1つの点について2回以上緩和が生じるようなグラフを入力と入れると、私の実装したアルゴリズムは破綻する。解決法は2つあって、

1. 条件はそのままで、上記の条件を保証する
2. 分岐を変更する

後者の方が楽そうなので、やってみる。->直したけど動かん！
模擬問題のページから入力引っ張ってきて行ったんだが、最初の入力でこける(出力される値が、1だけ多い)。前述の通り、サンプル入力に対する出力は正常だし、自分でグラフを適当に作成して出力をみてみてもちゃんと動いてるんだよなぁ。つまり、再現性の低いバグに出会ってしまったってことですね。多分最初から別のアルゴリズムで書き直した方が早いかなー。Dijkstraだけはとりあえず完成させたい…んだが、今回に限って言うと、ダメな入力というのがわからん。模擬ページの入力は、グラフがでかすぎて解析が困難だし。とりあえずDijkstraはこれでOKにするかな。