第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()