ダイクストラ法 （Pythonによるアルゴリズムとデータ構造）

本記事は、ソフトバンクパブリッシングから発行されている「定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)」を参考にPythonでアルゴリズムとデータ構造について学習していきます。

今回は、書籍には紹介されていませんが、ダイクストラ法（Dijkstra's Algorithm）について学んでいきます。

ダイクストラ法とは

ある地点から目的地までに複数の経路があり、その経路によってかかるコストが異なる場合は、目的地までの最適経路を求めることができます。

このような最適経路問題を解くためのアルゴリズムとしてダイクストラ法（Dijkstra's Algorithm）があります。

ダイクストラ法は、1959年にオランダの計算機科学者であるE.W.Dijkstraにより考案されました。

有名なルーティングプロトコルであるOSPF（Open Shortest Path First）やカーナビの経路探索などにも使われているアルゴリズムです。

ダイクストラ法では、全ての地点を未訪問、コストを無限大として初期化しておき、最小コストの地点があれば、それを更新していきます。

今回は以下のような経路情報があった場合、A地点からF地点までの最適経路を探索してみます。

なお、各ノード間の数字はコストを表しています。

fig1. A地点からF地点までの経路情報

Pythonでダイクストラ法を作成

それでは、Pythonでダイクストラ法を作成します。

# dijkstra.py
import sys

INF         = 10000
VISITED     = 1
NOT_VISITED = 0

route = [
    [INF, 2, 3, INF, INF, INF],
    [2, INF, 4, 3, 5, INF],
    [3, 4, INF, 6, 4, INF],
    [INF, 3, 6, INF, 1, 5],
    [INF, 5, 4, 1, INF, 3],
    [INF, INF, INF, 5, 3, INF]]

size = len(route)
cost = [INF for _ in range(size)]
visit = [NOT_VISITED for _ in range(size)]
before = [None for _ in range(size)]
cost[0] = 0
while True:
    min = INF
    for i in range(size):
        if visit[i] == NOT_VISITED and cost[i] < min:
            x = i
            min = cost[x]
    if min == INF:
        break
    visit[x] = VISITED
    print("visited to {}.".format(chr(65+x)))

    for i in range(size):
        if cost[i] > route[x][i] + cost[x]:
            cost[i] = route[x][i] + cost[x]
            before[i] = x

if cost[size-1] == INF:
    print("could not find optimum route.")
    sys.exit(1)

i = size - 1
optimum_route = []
while True:
    optimum_route.insert(0, chr(65+i))
    if i == 0:
        break
    i = before[i]

print("minimal cost is {}.".format(cost[size-1]))
print("optimum route is '", end="")
for i in range(len(optimum_route)):
    print(optimum_route[i], end="")
    if i == len(optimum_route) -1:
        print("'.")
        break
    print("->", end="")

動作確認 

それでは上記で作成したスクリプトを実行してみます。

 > python dijkstra.py
 visited to A.
 visited to B.
 visited to C.
 visited to D.
 visited to E.
 visited to F.
 minimal cost is 9.
 optimum route is 'A->B->D->E->F'.

問題なく最適経路を確認することができました。

参考書籍

やさしいC アルゴリズム編 (やさしいシリーズ)

定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)