networkx，摩尔邻域，最短路径问题

Question

我正在尝试在摩尔邻域中构建一个矩形图。在那里面，我正在寻找最短路径（nx.shortest_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)

正在搜索路径：

# 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 边最短路径，我看不出有什么问题。另一方面，如果我们考虑到边的 weight ，之字形不是最短路径。对于哪种情况，您必须使用：

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

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

为您提供以下路径：

networkx，摩尔邻域，最短路径问题

networkx, moore-neighbourhood, shortest path issue

python

shortest-path

networkx