![見出し画像](https://assets.st-note.com/production/uploads/images/13437362/rectangle_large_type_2_8eec7c6e43cab4c7b8f89e362289bc86.png?width=1200)
第k最短路
第k番目の最短経路を求める問題は,古典的なYenの解法や,よりモダンな高速化など色々研究されているが,networkXではYenの解法だけが実装されているようだ.
使うのは,(k-th shortest pathと銘打っていないので分かりにくいが)shortest_simple_pathsという関数だ.simpleというのは単純パスのことで,同じ点を2回以上通過しないパスのことだ.
格子グラフを作成して実験してみる.
n = 5
G = nx.grid_2d_graph(n,n)
pos ={(i,j):(i,j) for (i,j) in G.nodes() }
for (i,j) in G.edges():
G[i][j]["weight"] = random.randint(1,10)
グラフを描画するには,以下のようにする.
edge_labels = { (i,j):str(G[i][j]["weight"]) for (i,j) in G.edges() }
plt.figure()
nx.draw(G, pos=pos,with_labels=False, node_size=100)
nx.draw_networkx_edge_labels(G,pos,edge_labels=edge_labels)
plt.show()
第k最短路を得るためには,itertoolsのisliceでkを指定すればよい.
from itertools import islice
def path_length(G,path):
_sum = 0
i = path[0]
for count in range(1,len(path)):
j = path[count]
_sum += G[i][j]["weight"]
i = j
return _sum
k =10
for path in islice(nx.shortest_simple_paths(G, source=(0,0), target=(n-1,n-1), weight="weight"), k):
print(path, path_length(G,path))
>>>
[(0, 0), (0, 1), (1, 1), (1, 2), (2, 2), (2, 3), (2, 4), (3, 4), (4, 4)] 24
[(0, 0), (0, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 3), (4, 3), (4, 4)] 31
[(0, 0), (0, 1), (1, 1), (1, 2), (2, 2), (2, 3), (2, 4), (3, 4), (3, 3), (4, 3), (4, 4)] 31
[(0, 0), (0, 1), (1, 1), (1, 2), (1, 3), (2, 3), (2, 4), (3, 4), (4, 4)] 32
[(0, 0), (0, 1), (1, 1), (1, 2), (2, 2), (2, 3), (3, 3), (4, 3), (4, 4)] 32
[(0, 0), (0, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 3), (3, 4), (4, 4)] 32
[(0, 0), (0, 1), (0, 2), (1, 2), (2, 2), (2, 3), (2, 4), (3, 4), (4, 4)] 33
[(0, 0), (0, 1), (1, 1), (1, 2), (2, 2), (2, 3), (3, 3), (3, 4), (4, 4)] 33
[(0, 0), (1, 0), (1, 1), (1, 2), (2, 2), (2, 3), (2, 4), (3, 4), (4, 4)] 34
[(0, 0), (0, 1), (1, 1), (1, 2), (2, 2), (3, 2), (4, 2), (4, 3), (4, 4)] 35
得られた最後の(10番目の)パスを描画するには,以下のようにすればよい.冒頭にあげたような図が得られる.
edge_list =[]
i = path[0]
for count in range(1,len(path)):
j = path[count]
edge_list.append( (i,j) )
i = j
plt.figure()
nx.draw(G, pos=pos,with_labels=False, node_size=100)
nx.draw(G, pos=pos,with_labels=False, node_size=100, edgelist=edge_list,edge_color="red",width=10,alpha=0.3)
nx.draw_networkx_edge_labels(G,pos,edge_labels=edge_labels)
plt.show()
この記事が気に入ったらサポートをしてみませんか?