ダイクストラ法への道 第3弾です。いよいよダイクストラ法を使います。
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
201 96 342 965 150
630 803 746 422 111
537 699 497 121 956
805 732 524 37 331
これらのマスは最小経路和が確定です。
131 804 234 103 18
332 96 342 965 150
630 803 746 422 111
537 699 497 121 956
805 732 524 37 331
青のマスは、もう次に進んでしまったマスです。
次は、赤いマスで最小の最小経路和のマスに着目します。332のマスです。このマスから右と下に進むとそれがそのマスの最小経路和になります。なぜなら、これらのマスは赤いマスのどれかを必ず通るからです。
131 804 234 103 18
332 428 342 965 150
962 803 746 422 111
537 699 497 121 956
805 732 524 37 331
このようにすると、全てのマスの最小経路和を求めることができます。
赤いマスのうち最小経路和が最小のマスについて、未確定の隣のマスを赤にして、最小のマスは赤にします。しかし、最小のマスを選ぶのにたぶんO(N)程度かかるので（場合によってはO(N2)程度かかるかも）、全体でO(N3)程度かかると思われます。
ここでうってつけなのがPriorityQueueです。PriorityQueueにマスを入れてマスを取り出すと、それが最小のマスになっているので、それが青で、PriorityQueueの中に入っているマスが赤ということになります。これで全体の計算量はO(N2log N)となります。
以上がダイクストラ法の説明ですが、ScalaではPriorityQueueは最大の要素を取り出すので、PriorityQueueには(-最小経路和,x座標,y座標)を入れます。