networkx、moore-neighborhood、最短経路の問題

Question

私はムーア近所に長方形のグラフを作成しようとしています。その中で、私は最短経路（nx.shortest_path）を探していますが、奇妙な（ジグザグ）があります。

私は非常に確信しています。その理由は、グラフを作成する方法ですが、問題は見つけられません。

まず、Iはグリッドノードを構築：

#Building the Grid and the nodes 
resolution = 1 
length = 10 
index = 0 
xGrid = np.arange(0, length+1, resolution) 
yGrid = np.arange(0, length+1, resolution) 
G = nx.Graph() 
print(xGrid) 
meshNumber = np.zeros((length, length)) 
for i in range(length): 
    for j in range(length): 
     G.add_node(index, pos=(
      xGrid[j], yGrid[i])) 
     meshNumber[j,i] = index 
     index += 1 

そして、私は、パスを検索縁とその重み

# Building the edges 
diag = np.sqrt(2) * resolution 
for i in range(1, length-2): 
    for j in range(1, length-2): 
     if meshNumber[j, i]: 
      if meshNumber[j - 1, i]: 
       G.add_edge(
        meshNumber[j, i], meshNumber[j - 1, i], weight=resolution) 
      if meshNumber[j + 1, i]: 
       G.add_edge(
        meshNumber[j, i], meshNumber[j + 1, i], weight=resolution) 
      if meshNumber[j, i - 1]: 
       G.add_edge(
        meshNumber[j, i], meshNumber[j, i - 1], weight=resolution) 
      if meshNumber[j, i + 1]: 
       G.add_edge(
        meshNumber[j, i], meshNumber[j, i + 1], weight=resolution) 
      if meshNumber[j - 1, i - 1]: 
       G.add_edge(
        meshNumber[j, i], meshNumber[j - 1, i - 1], weight=diag) 
      if meshNumber[j - 1, i + 1]: 
       G.add_edge(
        meshNumber[j, i], meshNumber[j - 1, i + 1], weight=diag) 
      if meshNumber[j + 1, i + 1]: 
       G.add_edge(
        meshNumber[j, i], meshNumber[j + 1, i + 1], weight=diag) 
      if meshNumber[j + 1, i - 1]: 
       G.add_edge(
        meshNumber[j, i], meshNumber[j + 1, i - 1], weight=diag) 

をcalcuate：

プロット

# Finding the path 
start = 5 
end = 66 
try: 
    path = set(nx.shortest_path(G, start, end)) 

except nx.exception.NetworkXNoPath: 
    raise AssertionError("Could not find a good Path") 

：

# Plotting 
flatten = np.ones((index), dtype=np.int) 
for p in path: 
    flatten[int(p)] = 900 
flatten[start] = 1000 
flatten[end] = 1000 
colors = [] 
for f in flatten: 
    colors.append(str(f)) 
pos = nx.get_node_attributes(G, 'pos') 
fig = plt.figure(1, figsize=(12, 12), dpi=90) 
ax = fig.add_subplot(111) 
pos = nx.get_node_attributes(G, 'pos') 
nx.draw_networkx_nodes(G, pos, node_color=colors, node_size=500, alpha=0.8, 
         linewidths=3) 
nx.draw_networkx_edges(G, pos, width=1.0, alpha=0.5) 
nx.draw_networkx_edges(G, pos, width=4, alpha=0.5, edge_color='#6985a5') 
labels = nx.get_edge_attributes(G, 'weight') 
nx.draw_networkx_edge_labels(G, pos, edge_labels=labels) 
plt.savefig("zigzag.png") 
plt.show() 

Answer 1

その奇妙なジグザグは6つのエッジの有効な最短パスですが、私は問題が何かを見ていません。一方、ジグザグは、エッジの重量を考慮すると、最短パスではありません。その場合のためには、使用する必要があります。

try: 
    path = set(nx.shortest_path(G, start, end, weight='weight')) 

except nx.exception.NetworkXNoPath: 
    raise AssertionError("Could not find a good Path") 

はあなたの次のパス与える：