経路を探す

カーナビや電車乗換はどのようにして、通る道や乗る電車を探しているか考えたことがありますか。
出発する場所と通過する場所、 目的の場所を、単純な○と－を用いて「○―○―○」と表し、「グラフ理論」を利用すると、効率的に最短経路を計算できます。

最短経路を求める

最短経路を求めるアルゴリズムとして「ダイクストラ法」があります。1959年エドガー・ダイクストラによって考案されました。カーナビの経路探索や鉄道の乗換案内に利用されています。ダイクストラ法では、上記の「○」をノードと呼び、各ノードへの最短経路を、始点の周辺から１か所ずつ確定し徐々に範囲を広げていく方法で、以下のようなアルゴリズムです。

• 各地点までの距離を未確定とし、とりあえず「∞(無限大)」としておきます。
• 始点の距離を「0」とおきます。
• 未確定の地点の中から、距離が最も近い地点を選んで、その距離を『その地までの最短距離』として確定します。
• 直近で確定した地点から直接つながっていて「∞(無限大)」の地点に対して、直近で確定した場所を経由した場合の距離を計算し、今までの距離よりも小さければ「その地までの最短距離」として更新します。

グラフ理論（詳しく知りたい方向け）

グラフ理論の「グラフ」とは、さまざまなもの同士のつながり方を表したもので、さまざまなものとして使われているドットや丸で表すものを頂点（ノード）といい、その間をつなぐ線のことを辺（エッジ）といいます。ルート検索ではさまざまなものが場所であり、つなぐ線が経路でした。グラフを表現するのに図で表すだけではなく、コンピュータにもわかるように行列を使った表し方があります。

上のグラフの辺を一筆書きで書けるか考えてみましょう。
頂点に集まる辺の本数が奇数である点を奇点、偶数である点を偶点とします。一筆書きを始める点、途中通過する点、終わる点を考えてみると、途中通過する点は入って出るので必ず偶点となり、奇点は通過する点にはなれません。奇点から始めたとするとその奇点に戻って終わることはできず、違う奇点で終わる必要があります。よって奇点が1か3以上であると一筆書きができません。つまり、一筆書き可能なのは奇点の個数が0または2個のグラフのときとわかります。
上のグラフでは、aに集まる辺は3（=2+1）、bは5、cは3、dは3です。したがって、一筆書きはできないことがわかります。

関連動画

解説動画「社会・暮らし分野」