ダイクストラ法への道 第2弾です。
131 673 234 103 18 201 96 342 965 150 630 803 746 422 111 537 699 497 121 956 805 732 524 37 331
今度は右と下と上の隣のマスへ進めます。左の列から順に考えていきます。最も左の列は上から下への経路しかありません。
131 673 234 103 18
332 96 342 965 150
962 803 746 422 111
1499 699 497 121 956
2304 732 524 37 331
赤字は最小経路和が確定したマスでその最小経路和を示しています。さて、次の列を考えます。ここからは各マスへ経路が複数あります。最も左の列のマスを通ってくる経路も考えることができます。しかし、下の太字の673はその左の131から直接辿ってくる経路が最小経路です。
131 673 234 103 18
332 96 342 965 150
962 803 746 422 111
1499 699 497 121 956
2304 732 524 37 331
なぜなら、その131が左の列で最小なので左の列のどのマスを通ってもこれより経路和は小さくならないからです。これで673のマスの最小経路和は確定です。
131 804 234 103 18
332 96 342 965 150
962 803 746 422 111
1499 699 497 121 956
2304 732 524 37 331
次に確定済のマスのうちで各行で最も右のマスで最小の最小経路和のマスを考えます。なぜなら、残りのマスは必ずそのどれかを経由するからです。最小のマスは332ですね。だから、その右隣の96のマスの最小経路は332から直接辿ってくるものです。これで96のマスも確定です。
131 804 234 103 18
332 428 342 965 150
962 803 746 422 111
1499 699 497 121 956
2304 732 524 37 331
次も同様に考えますが、今度の確定済最小経路和のマスは342です。このときは、その下の746のマスへの最小経路が342から直接辿ってくることになります。
131 804 234 103 18
332 428 342 965 150
962 1174 746 422 111
1499 699 497 121 956
2304 732 524 37 331
このように最も右の列まで処理すると、全てのマスの最小経路和が求まります。ただ、最小のマスを求めるのにO(N)かかるので、全体ではO(N3)かかるんですね。
