最短経路を求める方法を勉強してみた!

出発点から目的地までの最短経路を求めるアルゴリズムを勉強してみた!

ダイクストラほうは、出発点ごろから目的地までの最短経路を求めるアルゴリズムとして有名である。

最短隣接地点を繰り返し求めていく

ダイクストラ方のアイデアは、出発点に隣接する地点までの経路を確定していき、最終的に目的にたどり着く手法である。

確定した地点を太い線で囲み、確定した経路を実践で示すことにする。

出発点である東京は確定しているため、太い線で囲んでおく。出発点であるため確定距離は0キロメートルとする。
東京に隣接しているのは高崎、長野、名古屋である。東京からの距離は、高崎510キロ、長野230キロ、名古屋350キロ。よって最短距離は高崎までの110キロで確定する。なぜなら他の地点を経由して高崎に行くと、長野または名古屋を経由することになるため、高崎に直接行く方法より長くなるからである。

このように現場確定している経路に隣接する地点が複数ある場合、その中にある最短の時点までの経路が確定する。これがダイクストラ方のその中にある最短の時点までの経路が確定する。これがダイクストラ方のアイディアである。