Pythonでのダイクストラ法見える化

Pythonでのダイクストラ法見える化

非情報工学出身ですが、最近業務でデータ処理する機会が増えてきた中、今回たまたま最短経路問題に関する疑問にぶつかりダイクストラ法について勉強してみたところ、理解に苦しんだ部分が多かったので備忘録としてダイクストラ法の処理の流れを視覚的にわかりやすく記す。networkx内関数で一気に解決できるが、今回はアルゴリズムの理解とコードのお勉強のために使わない。あくまで情報工学素人がまとめたものですので、より確実なものを求める方は参考サイトの方などを参照してください。

<参考サイト>

ダイクストラ法（最短経路問題） - deq notes

http://www.deqnotes.net/acmicpc/dijkstra/

Python ダイクストラ法 ( Dijkstra's algorithm ) で最短経路を求める

https://qiita.com/shizuma/items/e08a76ab26073b21c207

解析対象経路としては、参考サイトdeq notesのものと同じものを使用します。ノードが6個。無向グラフ。 初期情報として、各点から各点へのルートコストをまとめたリストが与えれるものとします。

route_list = [[0, 5, 4, 2, 0, 0], [5, 0, 2, 0, 0, 6], [4, 2, 0, 3, 2, 0],
              [2, 0, 3, 0, 6, 0], [0, 0, 2, 6, 0, 4], [0, 6, 0, 0, 4, 0]]

上記の情報で得られる経路はどのような形をしているのでしょうか？　どうせなら図もコードでということで図はnetworkxを使って描きます。

import networkx as nx
import matplotlib.pyplot as plt
%matplotlib inline

# ノード数、各エッジコストなどを初期情報route_listから取得
node_count = len(route_list)
edges = [[i, j, route_list[i][j]] for i in range(node_count) for j in range(node_count) if route_list[i][j] != 0]

G=nx.Graph() 

#6点準備。初期色は黒を指定
G.add_nodes_from(list(range(node_count)), color= "k")

# エッジコストも含め点を繋ぐ。初期色は黒を指定
G.add_weighted_edges_from(edges, color= "k")

# 座標設定
pos={} 
pos[0]=(0,0) 
pos[1]=(2,2) 
pos[2]=(3,0)
pos[3]=(1,-3)
pos[4]=(4,-2)
pos[5]=(5,1)

#ノード色をリスト化
node_labels = { n: d['color'] for n,d in G.nodes(data=True) }
node_colors = [ node_labels[key] for key in node_labels ]

#エッジの始点と終点の組合わせとエッジコストを辞書の形で格納。
#G.edge(data=True) でエッジセットを辞書の形で得れる。(Falseは(u, v)タプルのみ)
edge_labels_weight = { (u,v): d['weight'] for u,v,d in G.edges(data=True) }
edge_labels_colors = { (u,v): d['color'] for u,v,d in G.edges(data=True) }
edge_colors = [edge_labels_colors[key] for key in edge_labels_colors]

# 描画
nx.draw_networkx_labels(G, pos, font_color="w")
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels_weight)
nx.draw(G, pos, node_color=node_colors, edge_color=edge_colors)

plt.show() 

はい描けました。0をスタートとし5をゴールとします。0から5に辿り着くための最短経路を求めていきます。 ダイクストラ法は、「手近で明らかなことから順次確定していき，その確定した情報をもとにさらに遠くまで確定していく」方法です。 スタート時の未確定ノードは[0, 1, 2, 3, 4, 5]です。 まずはスタートノード0から見て一番近い未確定ノードは0です。これは明らかです。なので0は確定ノードとします。（コード上で0を確定するのは後ほどにします）

# 初期未確定ノードリスト
unfixed_nodes = list(range(6))

# 未確定ノードリストから0を除去
unfixed_nodes.remove(0)

# 未確定ノードリストに無いノードは確定したということで赤色に変える関数を定義します。
def changeColorOfFixedNode(node_colors, unfixed_nodes):
    diff = list(set(list(range(6))) - set(unfixed_nodes))
    for d in diff:
        node_colors[d] = "r"
    return node_colors


node_colors = changeColorOfFixedNode(node_colors, unfixed_nodes)

nx.draw_networkx_labels(G, pos, font_color="w")
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels_weight)
nx.draw(G,pos, node_color=node_colors)
plt.show()

確定ノードは赤色に変えていきます。

ここから本格的にスタートしていきます。未確定ノードは[1, 2, 3, 4, 5]です。これらの点はスタートからの最短距離が確定していません。 スタートノードからの最短距離リストを作成します。スタートノード以外の点のスタートノードからの最短距離は確定していませんので、現状は値を∞に設定します。

import math
minimum_distances_from_startnode = [math.inf] * node_count
minimum_distances_from_startnode[0] = 0
minimum_distances_from_startnode

[0, inf, inf, inf, inf, inf]

さて、では確定できそうなノード探しをしていきます。まずはスタートノードから一番距離が近い点はどこか、その距離はどのくらいか、これを知りたいです。 スタートノードから出ているエッジとその先の点、距離はroute_list[0]によって与えれています。その中で一番近い点はどこでしょうか。 距離探索の初期値を∞として、もしその値よりも小さい距離が見つかれば更新するという手順で探します。距離0はエッジが繋がっていないか自身までの距離を指すため除外します。

possible_min_distance = math.inf
for route in route_list[0]:
    if route == 0:
        continue
    else:
        if possible_min_distance > route:
            possible_min_distance = route
closest_node = route_list[0].index(possible_min_distance)
print ("possible_min_distance = " + str(possible_min_distance))
print ("closest_node = " + str(closest_node))

possible_min_distance = 2
closest_node = 3

3番ノードが距離2で一番近いことがわかりました。スタートノードに繋がっているノード内で一番近いということなので、もし負のコストを持つエッジが存在しなければ距離2よりも少ない最短経路が見つかることはありません。（これが負のコストを持つエッジが存在する場合はダイクストラ法を使えない理由です） よって3番ノードを確定ノードとして未確定ノードから除去しましょう。

unfixed_nodes.remove(closest_node)

#(0, 3)のエッジも最短距離として確定したので赤色に。
edge_labels_colors[(0, 3)] = "r"
edge_colors = [edge_labels_colors[key] for key in edge_labels_colors]

node_colors = changeColorOfFixedNode(node_colors, unfixed_nodes)
nx.draw_networkx_labels(G, pos, font_color="w")
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels_weight)
nx.draw(G,pos, node_color=node_colors, edge_color=edge_colors)
plt.show()

さて次の確定探しに移ります。 3番が未確定ノードから抜けましたので今の未確定ノードリストは[1, 2, 4, 5]です。それぞれスタートノードからの距離minimum_distances_from_startnodeとして判明しているものは1番距離5, 2番距離4のみで、他は不明なため∞です。先程のスタートノードからの探索の際にこれを記憶させておかないといけなかったですね。 探索していく際に、現在のminimum_distances_from_startnodeよりも短い距離が見つかった際にはこれを更新していく仕組みが必要でした。

for i, route in enumerate(route_list[0]):
    if route == 0:
        continue
    else:
        if possible_min_distance > route:
            possible_min_distance = route
        minimum_distances_from_startnode[i] = route
minimum_distances_from_startnode

[0, 5, 4, 2, inf, inf]

スタートノードからの最短距離リストが更新されました（本当は上記では不十分ですが、ひとまずここでは良しとします）。 この中で未確定ノードの内、一番短いのは2番ノードの距離4です。が今回確定した3番ノードからもエッジが伸びていますので、3番ノードからの距離を調べて、比較する必要があります。 まずは最短距離リストから2番ノード距離4が未確定ノードの中で最短であることを導き出すコードを書きましょう

possible_min_distance_from_startnode = math.inf
for node_index in unfixed_nodes:
    if possible_min_distance_from_startnode > minimum_distances_from_startnode[node_index]:
        possible_min_distance_from_startnode = minimum_distances_from_startnode[node_index]
        min_distance_node = node_index
print ("possible_min_distance_from_startnode = " + str(possible_min_distance_from_startnode))
print ("min_distance_node = " + str(min_distance_node))

possible_min_distance_from_startnode = 4
min_distance_node = 2

2番距離4が未確定ノードの内スタートノードからの距離が最短であることがわかりましたが、2番へ到達するには、4本のルートがありますのでもしかしたらスタートノードから他を経由した方が短いかもしれませんので調べます。 2番から伸びるエッジのリストroute_list[2]のコストと各ノードまでのスタートノードからの距離minimum_distances_from_startnodeの合計が、現在のスタートノードから2番までの最短距離よりも小さければこちらの方が短いということになるので更新します。もし更新された場合は、その最短距離を出したルートの2番に着く１つ前にいた確定ノード番号を記憶します。

min_distance_node_edges = route_list[min_distance_node]
previous_fixed_nodes = [-1]*node_count
# [-1, -1, -1, -1, -1, -1] 初期値は-1として、各ノードに辿り着く最短ルートにおいて１つ前の確定ノードを入れる。
# 今回は途中からの変数作成のため、マニュアルで値を代入します。
previous_fixed_nodes = [-1, 0, 0, 0, -1, -1]
for i, min_distance_node_edge in enumerate(min_distance_node_edges):
    if min_distance_node_edge == 0:
        continue
    else:
        if minimum_distances_from_startnode[min_distance_node] > min_distance_node_edge + minimum_distances_from_startnode[i]:
                minimum_distances_from_startnode[min_distance_node] = min_distance_node_edge + minimum_distances_from_startnode[i]
                previous_fixed_nodes[i] = i

print ("minimum_distances_from_startnode[{min_distance_node}] = ".format(min_distance_node=min_distance_node) + str(minimum_distances_from_startnode[min_distance_node]))
print ("previous_fixed_nodes = " + str(previous_fixed_nodes))

minimum_distances_from_startnode[2] = 4
previous_fixed_nodes = [-1, 0, 0, 0, -1, -1]

これで2番が確定したので未確定ノードリストから除去します。

unfixed_nodes.remove(min_distance_node)

fixed_edge = (previous_fixed_nodes[min_distance_node], min_distance_node) 
edge_labels_colors[fixed_edge] = "r"
edge_colors = [edge_labels_colors[key] for key in edge_labels_colors]

node_colors = changeColorOfFixedNode(node_colors, unfixed_nodes)
nx.draw_networkx_labels(G, pos, font_color="w")
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels_weight)
nx.draw(G,pos, node_color=node_colors, edge_color=edge_colors)
plt.show()

このサイクルを回して行き、未確定ノードを潰していきます。 では次の1番ノードを確定するまでを一気にやってみます。またminimun_distances_from_startnode=[0, 5, 4, 2, 6, Inf], previous_fixed_nodes=[0, 0, 0, 0, 2, -1]からスタートします。

minimum_distances_from_startnode = [0, 5, 4, 2, 6, math.inf]
previous_fixed_nodes = [-1, 0, 0, 0, 2, -1]
possible_min_distance_from_startnode = math.inf
for node_index in unfixed_nodes:
    if possible_min_distance_from_startnode > minimum_distances_from_startnode[node_index]:
        possible_min_distance_from_startnode = minimum_distances_from_startnode[node_index]
        min_distance_node = node_index
min_distance_node_edges = route_list[min_distance_node]
for i, min_distance_node_edge in enumerate(min_distance_node_edges):
    if min_distance_node_edge == 0:
        continue
    else:
        if minimum_distances_from_startnode[i] > min_distance_node_edge + minimum_distances_from_startnode[min_distance_node]:
                minimum_distances_from_startnode[i] = min_distance_node_edge + minimum_distances_from_startnode[min_distance_node]
                previous_fixed_nodes[i] = min_distance_node
unfixed_nodes.remove(min_distance_node)

print ("possible_min_distance_from_startnode = " + str(possible_min_distance_from_startnode))
print ("min_distance_node = " + str(min_distance_node)) 
print ("minimum_distances_from_startnode = " + str(minimum_distances_from_startnode))
print ("minimum_distances_from_startnode[{min_distance_node}] = ".format(min_distance_node=min_distance_node) + str(minimum_distances_from_startnode[min_distance_node]))
print ("previous_fixed_nodes = " + str(previous_fixed_nodes))
print ("unfixed_nodes = " + str(unfixed_nodes))

fixed_edge = (previous_fixed_nodes[min_distance_node], min_distance_node) 
edge_labels_colors[fixed_edge] = "r"
edge_colors = [edge_labels_colors[key] for key in edge_labels_colors]

node_colors = changeColorOfFixedNode(node_colors, unfixed_nodes)
nx.draw_networkx_labels(G, pos, font_color="w")
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels_weight)
nx.draw(G,pos, node_color=node_colors, edge_color=edge_colors)
plt.show()

possible_min_distance_from_startnode = 5
min_distance_node = 1
minimum_distances_from_startnode = [0, 5, 4, 2, 6, 11]
minimum_distances_from_startnode[1] = 5
previous_fixed_nodes = [-1, 0, 0, 0, 2, 1]
unfixed_nodes = [4, 5]

これで1番が確定しました。 あとは今までのフローを繰り返せば良いだけですので、4番5番の確定までループ処理するように改修して回します。 全てのノードの確定が完了したことを認識するためには未確定ノードリストがなくなったことを条件にします。またminimum_distances

while len(unfixed_nodes) != 0:
    possible_min_distance_from_startnode = math.inf
    for node_index in unfixed_nodes:
        if possible_min_distance_from_startnode > minimum_distances_from_startnode[node_index]:
            possible_min_distance_from_startnode = minimum_distances_from_startnode[node_index]
            min_distance_node = node_index
    min_distance_node_edges = route_list[min_distance_node]
    for i, min_distance_node_edge in enumerate(min_distance_node_edges):
        if min_distance_node_edge == 0:
            continue
        else:
            if minimum_distances_from_startnode[i] > min_distance_node_edge + minimum_distances_from_startnode[min_distance_node]:
                    minimum_distances_from_startnode[i] = min_distance_node_edge + minimum_distances_from_startnode[min_distance_node]
                    previous_fixed_nodes[i] = min_distance_node
    unfixed_nodes.remove(min_distance_node)

    print ("possible_min_distance_from_startnode = " + str(possible_min_distance_from_startnode))
    print ("min_distance_node = " + str(min_distance_node))
    print ("minimum_distances_from_startnode = " + str(minimum_distances_from_startnode))
    print ("minimum_distances_from_startnode[{min_distance_node}] = ".format(min_distance_node=min_distance_node) + str(minimum_distances_from_startnode[min_distance_node]))
    print ("previous_fixed_nodes = " + str(previous_fixed_nodes))
    print ("unfixed_nodes = " + str(unfixed_nodes))

    fixed_edge = (previous_fixed_nodes[min_distance_node], min_distance_node) 
    edge_labels_colors[fixed_edge] = "r"
    edge_colors = [edge_labels_colors[key] for key in edge_labels_colors]

    node_colors = changeColorOfFixedNode(node_colors, unfixed_nodes)
    nx.draw_networkx_labels(G, pos, font_color="w")
    nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels_weight)
    nx.draw(G,pos, node_color=node_colors, edge_color=edge_colors)
    plt.show()
    

possible_min_distance_from_startnode = 6
min_distance_node = 4
minimum_distances_from_startnode = [0, 5, 4, 2, 6, 10]
minimum_distances_from_startnode[4] = 6
previous_fixed_nodes = [-1, 0, 0, 0, 2, 4]
unfixed_nodes = [5]

possible_min_distance_from_startnode = 10
min_distance_node = 5
minimum_distances_from_startnode = [0, 5, 4, 2, 6, 10]
minimum_distances_from_startnode[5] = 10
previous_fixed_nodes = [-1, 0, 0, 0, 2, 4]
unfixed_nodes = []

これで完了です。グラフを見ると最短経路は0->2->4->5の距離10ですね。 どうせならこれをコードで出すようにしましょうか。情報はprevious_fixed_nodesとminimum_distances_from_startnodeから得れますね。 ゴールである5番ノードから逆に辿っていきます

print("-----経路-----")
previous_node = node_count - 1
while previous_node != -1:
    if previous_node !=0:
        print(str(previous_node) + " <- ", end='')
    else:
        print(str(previous_node))
    previous_node = previous_fixed_nodes[previous_node]

print("-----距離-----")
print(minimum_distances_from_startnode[node_count - 1])

-----経路-----
5 <- 4 <- 2 <- 0
-----距離-----
10

はいこれで本当に完了です！ ダイクストラ法の流れが少しでもつかめましたでしょうか？僕はこれを書くことでだいぶ理解できたので満足です。 最後にひとまとめのコードを書いておきます。

%reset
route_list = [[0, 5, 4, 2, 0, 0], [5, 0, 2, 0, 0, 6], [4, 2, 0, 3, 2, 0],
              [2, 0, 3, 0, 6, 0], [0, 0, 2, 6, 0, 4], [0, 6, 0, 0, 4, 0]]

import networkx as nx
import matplotlib.pyplot as plt
import math
%matplotlib inline

# ノード数、各エッジコストなどを初期情報route_listから取得
node_count = len(route_list)
edges = [[i, j, route_list[i][j]] for i in range(node_count) for j in range(node_count) if route_list[i][j] != 0]

G=nx.Graph() 

#6点準備。初期色は黒を指定
G.add_nodes_from(list(range(node_count)), color= "k")

# エッジコストも含め点を繋ぐ。初期色は黒を指定
G.add_weighted_edges_from(edges, color= "k")

# 座標設定
pos={} 
pos[0]=(0,0) 
pos[1]=(2,2) 
pos[2]=(3,0)
pos[3]=(1,-3)
pos[4]=(4,-2)
pos[5]=(5,1)

#ノード色をリスト化
node_labels = { n: d['color'] for n,d in G.nodes(data=True) }
node_colors = [ node_labels[key] for key in node_labels ]

#エッジの始点と終点の組合わせとエッジコストを辞書の形で格納。
#G.edge(data=True) でエッジセットを辞書の形で得れる。(Falseは(u, v)タプルのみ)
edge_labels_weight = { (u,v): d['weight'] for u,v,d in G.edges(data=True) }
edge_labels_colors = { (u,v): d['color'] for u,v,d in G.edges(data=True) }
edge_colors = [edge_labels_colors[key] for key in edge_labels_colors]

# 描画
nx.draw_networkx_labels(G, pos, font_color="w")
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels_weight)
nx.draw(G, pos, node_color=node_colors, edge_color=edge_colors)

plt.show() 

def changeColorOfFixedNode(node_colors, unfixed_nodes):
    diff = list(set(list(range(6))) - set(unfixed_nodes))
    for d in diff:
        node_colors[d] = "r"
    return node_colors

minimum_distances_from_startnode = [math.inf] * node_count
minimum_distances_from_startnode[0] = 0
unfixed_nodes = list(range(6))
previous_fixed_nodes = [-1]*node_count

while len(unfixed_nodes) != 0:
    possible_min_distance_from_startnode = math.inf
    for node_index in unfixed_nodes:
        if node_index == 0:
            possible_min_distance_from_startnode = 0
            min_distance_node = 0
        if possible_min_distance_from_startnode > minimum_distances_from_startnode[node_index]:
            possible_min_distance_from_startnode = minimum_distances_from_startnode[node_index]
            min_distance_node = node_index
    min_distance_node_edges = route_list[min_distance_node]
    for i, min_distance_node_edge in enumerate(min_distance_node_edges):
        if min_distance_node_edge == 0:
            continue
        else:
            if minimum_distances_from_startnode[i] > min_distance_node_edge + minimum_distances_from_startnode[min_distance_node]:
                    minimum_distances_from_startnode[i] = min_distance_node_edge + minimum_distances_from_startnode[min_distance_node]
                    previous_fixed_nodes[i] = min_distance_node
    unfixed_nodes.remove(min_distance_node)

    print ("possible_min_distance_from_startnode = " + str(possible_min_distance_from_startnode))
    print ("min_distance_node = " + str(min_distance_node))
    print ("minimum_distances_from_startnode = " + str(minimum_distances_from_startnode))
    print ("minimum_distances_from_startnode[{min_distance_node}] = ".format(min_distance_node=min_distance_node) + str(minimum_distances_from_startnode[min_distance_node]))
    print ("previous_fixed_nodes = " + str(previous_fixed_nodes))
    print ("unfixed_nodes = " + str(unfixed_nodes))
    
    if min_distance_node != 0:
        fixed_edge = (previous_fixed_nodes[min_distance_node], min_distance_node) 
        edge_labels_colors[fixed_edge] = "r"
        edge_colors = [edge_labels_colors[key] for key in edge_labels_colors]

    node_colors = changeColorOfFixedNode(node_colors, unfixed_nodes)
    nx.draw_networkx_labels(G, pos, font_color="w")
    nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels_weight)
    nx.draw(G,pos, node_color=node_colors, edge_color=edge_colors)
    plt.show()
    
print("-----経路-----")
previous_node = node_count - 1
while previous_node != -1:
    if previous_node !=0:
        print(str(previous_node) + " <- ", end='')
    else:
        print(str(previous_node))
    previous_node = previous_fixed_nodes[previous_node]

print("-----距離-----")
print(minimum_distances_from_startnode[node_count - 1])

possible_min_distance_from_startnode = 0
min_distance_node = 0
minimum_distances_from_startnode = [0, 5, 4, 2, inf, inf]
minimum_distances_from_startnode[0] = 0
previous_fixed_nodes = [-1, 0, 0, 0, -1, -1]
unfixed_nodes = [1, 2, 3, 4, 5]

possible_min_distance_from_startnode = 2
min_distance_node = 3
minimum_distances_from_startnode = [0, 5, 4, 2, 8, inf]
minimum_distances_from_startnode[3] = 2
previous_fixed_nodes = [-1, 0, 0, 0, 3, -1]
unfixed_nodes = [1, 2, 4, 5]

possible_min_distance_from_startnode = 4
min_distance_node = 2
minimum_distances_from_startnode = [0, 5, 4, 2, 6, inf]
minimum_distances_from_startnode[2] = 4
previous_fixed_nodes = [-1, 0, 0, 0, 2, -1]
unfixed_nodes = [1, 4, 5]

possible_min_distance_from_startnode = 5
min_distance_node = 1
minimum_distances_from_startnode = [0, 5, 4, 2, 6, 11]
minimum_distances_from_startnode[1] = 5
previous_fixed_nodes = [-1, 0, 0, 0, 2, 1]
unfixed_nodes = [4, 5]

possible_min_distance_from_startnode = 6
min_distance_node = 4
minimum_distances_from_startnode = [0, 5, 4, 2, 6, 10]
minimum_distances_from_startnode[4] = 6
previous_fixed_nodes = [-1, 0, 0, 0, 2, 4]
unfixed_nodes = [5]

possible_min_distance_from_startnode = 10
min_distance_node = 5
minimum_distances_from_startnode = [0, 5, 4, 2, 6, 10]
minimum_distances_from_startnode[5] = 10
previous_fixed_nodes = [-1, 0, 0, 0, 2, 4]
unfixed_nodes = []

-----経路-----
5 <- 4 <- 2 <- 0
-----距離-----
10