拡張ダイクストラ法を記述する

N、Mがオートマトン、S=|N|, T=|M|は状態集合。s0, t0はスタートノード。次がアルゴリズムのステップごとの入力になる。

1. 候補辺集合 C⊆S×T、Cは空ではない。
2. 確定辺集合 D⊆S×T、Dは空でもよい。
3. 調べるべき候補辺 r∈C

CとDを更新してステップの結果とする。

1. r∈D ならば、Cからrを削除して終り。
2. r = (s, t) として、sにダイクストラ法（ホイヘンス原理）を適用する。
3. 失敗したら、アルゴリズム全体が失敗。サヨナラ。
4. 成功したら、rと他の辺（1本または3本）をDに追加する。
5. Cからrを削除する。
6. 新しい波頭集合をCと合併する（波頭集合は空かもしれない）。

全体の制御は：

1. 初期状態は、C = {(s0, t0)} D = {} とする。
2. ステップの実行後にCが空になれば成功。Dが最大模倣を与える。
3. ゴールノードの対を (s1, t1) として、(s1, t1)∈D を調べる。YESなら成功、NOなら失敗。
4. ステップ内で失敗すれば、N上のダイクストラ波動に対するM上の模倣波動（simulation wave）を作れないことだから、アルゴリズム全体が失敗。

と、こうしてみると、拡張ダイクストラ法のキモは、お膳立ての部分だな。事前にオートマトンをいじって標準形にしておけば後は造作無い。特に無音遷移パスの長さを1に限定するのがポイント。これによって、複雑化と計算負荷の元凶である無音遷移の取り扱いを現実的にしている。

無音遷移は単なる悪者ではなくて、遷移の逆流や混線を防いでくれる。無音遷移なしでサイクルの処理はできない。本質的に役に立つヤツなんだが、いかんせんコストが高いので無駄に増やしたくはないのだ。

ここまで煮詰まれば、後は知的肉体労働あるのみ。

1. 実験
2. 改善と変更
3. テスト
4. 完全に場合分けして、細部まで証明

改善に関しては、実行用オートマトンと共用にする手段だな。それができれば、コンパイラ実装の手間はだいぶ減る。

最終的には割とコンパクトな実務的アルゴリズムになりそうだ。（が、まだ安心はできん）