networkx, 무어 - 이웃, 최단 경로 문제

Question

무어 인근에서 직사각형 그래프를 작성하려고합니다. 그 안에는 최단 경로 (nx.shortest_path)를 찾고 있지만 이상한 (지그재그) 이 나옵니다.

나는 그 이유가 그래프를 작성하는 방법이지만, 문제는 찾을 수 없다.

첫째, 나는 그리드와 노드 구축 :

# 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") 

플로팅 : 다음

#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 :

# 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") 

는 당신에게 다음과 같은 경로주기 :