talosのプログラミング教室

【超基本】初心者に贈るアルゴリズム論 ~ダイクストラ法~

スポンサーリンク

はじめに

こんにちは.talosです.

今回はダイクストラ法の説明をします.

ダイクストラ法は最短経路問題でよく使われるアルゴリズムなので,ぜひ覚えてください.

最短経路問題

最短経路問題とは,重み付きグラフが与えられたとき,2つの頂点間の重みが最小(距離が最短)となるような経路を求める問題です.

最短経路問題は3つに分けられます.

2頂点対最短経路問題

2つの頂点が与えられ,それらの最短経路を求める問題

単一始点最短経路問題

1つの頂点が与えられ,その頂点からその他のすべての頂点までの最短経路を求める問題

全頂点対最短経路問題

グラフ内のすべての2頂点の組み合わせについての最短経路を求める問題

ダイクストラ

ダイクストラは単一始点最短経路問題で使われる方法です.

すべての経路を計算するより計算量を減らすことができます.

アルゴリズムは以下のようになっています.

集合Xに属する頂点だけを通る経路だけに限定して始点sからの最短経路を求める手続きである.集合Xを始点sだけを含む初期状態から全頂点集合になるまで順次拡大していけば,最終的に正しい最短経路が求まる.具体的には,D[u]によって始点sから頂点uまでの最短経路の長さ,つまり頂点uの距離を表すことにする.集合Xの頂点uについては距離D[u]が正しく求められていれば,集合Xの外にあってXの頂点uと辺で結ばれている頂点vに対して,uを経由してvに至る最短経路の長さをD[u]+c(u,v)として求めることができる.この長さが頂点vに対して以前に求まっている最短経路の長さよりも短いなら,D[u]=D[u]+c(u,v)(ママ)として新たな経路の長さを記録しておく.Xの外の頂点でD[.]の値が最小である頂点をuとすると,uまでの最短経路は上記の操作で求められていることがわかる.したがって,uをXに加えて次のステップに進むことができる.


引用:「アルゴルズム論」|浅野哲夫,和田幸一,増澤利光

※ D[u]=D[u]+c(u,v)は間違いで正しくはD[v]=D[u]+c(u,v)です.

例えば,以下のようなグラフの最短経路を求めるとします.(グラフはページ下部の参考文献を参考に作成)

f:id:talosta:20190721154044p:plain

始点s以外へのコストは∞で初期化します.

そうしたら,初めにsをXに入れてあげましょう.

f:id:talosta:20190721213414p:plain

次に,Xの要素はsだけなので,sから到達できる頂点までのコストを更新します.

あとはひたすらこの作業を繰り返します.

f:id:talosta:20190721214107p:plain

sから一番近い頂点dをXに入れます

f:id:talosta:20190721214154p:plain

Xの要素にdが加わったので,dから到達できる頂点までのコストを更新します.

しかし,dから到達できる頂点はeのみで,sから向かった方が近いので変更はなしです.

sから二番目に近いaをXに入れます.(eも距離は同じですが,ここではアルファベット順とします.)

f:id:talosta:20190721223839p:plain

aから到達できる頂点までのコストを更新します.

f:id:talosta:20190721224020p:plain

以下,こんな感じです.

eを追加
f:id:talosta:20190721224202p:plain

c,f更新
f:id:talosta:20190721224317p:plain

fを追加
f:id:talosta:20190721224433p:plain

b,g更新
f:id:talosta:20190721224549p:plain

bを追加
f:id:talosta:20190721224626p:plain

cを更新
f:id:talosta:20190721224646p:plain

gを追加
f:id:talosta:20190721224723p:plain

hを更新
f:id:talosta:20190721224751p:plain

cを追加
f:id:talosta:20190721224826p:plain

hを更新
f:id:talosta:20190721224848p:plain

hを追加
f:id:talosta:20190721224938p:plain

実装例

上で挙げた図の最短経路を求めるプログラムです.

M = 1000          # 無限
node = 'sabcdefgh'  # 出力用

# 重み付き有向グラフ
g = [[M, 2, M, M, 1, 2, M, M, M],  # s
    [M, M, 3, M, M, M, 4, M, M],   # a
    [M, M, M, 1, M, M, M, M, M],   # b
    [M, M, M, M, M, M, M, M, 1],   # c
    [M, M, M, M, M, 3, M, M, M],   # d
    [M, M, M, 4, M, M, 2, M, M],   # e
    [M, M, 0.5, M, M, M, M, 1, M], # f
    [M, M, M, M, M, M, M, M, 2],   # g
    [M, M, M, M, M, M, M, M, M]]   # h

def dijkstra(s):
    # 初期化
    cost = [M] * len(g)     # 重み
    visit = [0] * len(g)    # 訪問済み or 未訪問
    parent = [-1] * len(g)  # 親ノード
    
    # 始点へのコストは0
    cost[s] = 0
    
    for i in range(len(g)):
        mini = M  # 最小コスト
        for j in range(len(g[s])):
            # 一番近いノードを探す
            if visit[j] == 0 and cost[j] < mini:
                mini = cost[j]
                u = j
        
        visit[u] = 1
        print('add:' + node[u])
        
        for j in range(len(g[s])):
            # 他のノードを経由して距離が短くなるなら経路を更新
            if cost[u] + g[u][j] < cost[j]:
                cost[j] = cost[u] + g[u][j]
                parent[j] = u
        
        print(cost)
            
    print('\n--result--')
    for i in range(1, len(g)):
        print('cost from ' + node[s] + ' to ' + node[i] +' is ' + str(cost[i]))
        print(node[i] + '\'s parent is ' + node[parent[i]] + '\n')

dijkstra(0)
add:s
[0, 2, 1000, 1000, 1, 2, 1000, 1000, 1000]
add:d
[0, 2, 1000, 1000, 1, 2, 1000, 1000, 1000]
add:a
[0, 2, 5, 1000, 1, 2, 6, 1000, 1000]
add:e
[0, 2, 5, 6, 1, 2, 4, 1000, 1000]
add:f
[0, 2, 4.5, 6, 1, 2, 4, 5, 1000]
add:b
[0, 2, 4.5, 5.5, 1, 2, 4, 5, 1000]
add:g
[0, 2, 4.5, 5.5, 1, 2, 4, 5, 7]
add:c
[0, 2, 4.5, 5.5, 1, 2, 4, 5, 6.5]
add:h
[0, 2, 4.5, 5.5, 1, 2, 4, 5, 6.5]

--result--
cost from s to a is 2
a's parent is s

cost from s to b is 4.5
b's parent is f

cost from s to c is 5.5
c's parent is b

cost from s to d is 1
d's parent is s

cost from s to e is 2
e's parent is s

cost from s to f is 4
f's parent is e

cost from s to g is 5
g's parent is f

cost from s to h is 6.5
h's parent is c

おわりに

今回はダイクストラ法について説明しました.

次回は動的計画法を用いてナップサック問題を解いていこうと思います.