[PR]当サイトはアフィリエイト広告を利用しています。
いよいよダイクストラ法のプログラムです。
ここまで長かったですね。
今回対象とするグラフはこれまで出てきた以下のグラフです。
いきなりですがプログラムです。
graph = [[None,1,3,None,None,None,None],[1,None,2,None,None,None,None],[3,2,None,2,2,4,None],[None,None,2,None,None,1,None],[None,None,2,None,None,5,3],[None,None,4,1,5,None,1],[None,None,None,None,3,1,None]]
parent = []
check = []
cost = []
for i in range(len(graph)):
parent.append(None)
check.append(False)
cost.append(None)
active = 0
cost[active] = 0
end = 6
while False in check:
check[active] = True
for i in range(len(graph)):
if(graph[active][i] is not None):
if(cost[i] is None):
cost[i] = cost[active] + graph[active][i]
parent[i] = active
else:
temp = cost[active] + graph[active][i]
if (cost[i] > temp):
cost[i] = temp
parent[i] = active
for i in range(len(graph)):
if((cost[i] is not None) and check[i] == False):
minIndex = i
minValue = cost[i]
break
for i in range(minIndex + 1, len(graph)):
if((cost[i] is not None) and check[i] == False):
if(cost[i] < minValue):
minValue = cost[i]
minIndex = i
active = minIndex
print("costTable")
print(cost)
print("parentTable")
print(parent)
path = []
def route(parent, end, path):
path.append(end)
if(parent[end] is not None):
route(parent, parent[end],path)
else:
return
route(parent, end, path)
path.reverse()
print("pathToEnd")
print(path)
print("costToEnd:" + str(cost[end]))ノード数7なので7行7列の隣接行列です。
今回は隣接していたらコストを、隣接していなければNoneを格納します。
隣接していなければ0としたいところですが、コスト0の隣接も存在するので、Noneにしています。
ノードの名前はAからGで表していましたが、[A,B,C,D,E,F,G]を[0,1,2,3,4,5,6]に変換しています。
parent = []
check = []
cost = []
for i in range(len(graph)):
parent.append(None)
check.append(False)
cost.append(None)2行目から8行目。
ノードの親を格納するparentと、確定したかどうか格納するcheckと、ノードのコストを格納するcostの3つのリストを宣言して、初期値を格納しています。
active = 0
cost[active] = 0
end = 69行目から11行目。
直近の確定ノードを表すactiveに最初の確定ノード0を格納。
最初の確定ノードのコストを0に設定。
ゴールのノードをendとして、その値を6(G)に設定。
while False in check:
check[active] = True
for i in range(len(graph)):
if(graph[active][i] is not None):
if(cost[i] is None):
cost[i] = cost[active] + graph[active][i]
parent[i] = active
else:
temp = cost[active] + graph[active][i]
if (cost[i] > temp):
cost[i] = temp
parent[i] = active12から23行目。
12行目ですべてのノードが確定ノードになるまで繰り返し。
13行目で現在のactiveのノードを確定ノードに決定。最初はノード0が確定されます。
今後activeはチャレンジノードの中の最小コストとなるノードが格納されることになります。
14から23行目。
確定ノードの隣接ノードを探してチャレンジ。
まだコストがないチャレンジしていないノードがあったら、そのノードへのコストを算出してcostに格納（16～18行目）。親を直近の確定ノードにする。
すでにチャレンジが行われていたノードなら、コストを算出したのち、現在のノードのコストと比較して、コストが下がればコストと親を更新（20から23行目）。
for i in range(len(graph)):
if((cost[i] is not None) and check[i] == False):
minIndex = i
minValue = cost[i]
break
for i in range(minIndex + 1, len(graph)):
if((cost[i] is not None) and check[i] == False):
if(cost[i] < minValue):
minValue = cost[i]
minIndex = i
active = minIndex24から34行目。
チャレンジノードの最小コストとなるノードを見つける処理。
まず確定していないチャレンジノードを探す（24～28行目）。
見つかったらそれ以外のチャレンジノードとコストを比較して小さければ、最小のチャレンジノードを順次更新して最小コストのチャレンジノードを求める（29～33行目）。
求めたチャレンジノードを次の確定ノードとするためactiveに設定。
activeは13行目に戻って確定ノードになる。
print("costTable")
print(cost)
print("parentTable")
print(parent)35～38行目。
求めた各ノードのコストとその親を表示。
path = []
def route(parent, end, path):
path.append(end)
if(parent[end] is not None):
route(parent, parent[end],path)
else:
return
route(parent, end, path)
path.reverse()39～47行目。
親のリストparentから実際にルートを求める関数routeを作成。
再帰処理です。
ゴールノードendから始まって、スタートノード0（親はないのでNoneになる）になるまで、endの親を呼び出してリストpathに格納していきます。
47行目でpathを逆から読むことでスタートからのルートに変換しています。
print("pathToEnd")
print(path)
print("costToEnd:" + str(cost[end]))48～50行目。
求めたルートとスタートからゴールまでのコストを表示しています。
プログラムを走らせた出力は以下です。
costTable
[0, 1, 3, 5, 5, 6, 7]
parentTable
[None, 0, 0, 2, 2, 3, 5]
pathToEnd
[0, 2, 3, 5, 6]
costToEnd:7
以前の記事で手作業で求めたコストと親はこんな感じ。
ちゃんと求めることができていますね。
以上で解説を終わります。
長かったダイクストラ法の解説もここで一段落です。
ゲームで実際にダイクストラ法が使われているかは定かではありませんが、もしかしたらこういうアルゴリズムがゲームを支えているのかもしれませんね。
