代码之家 › 专栏 › 技术社区 › Anathapindika

networkx、moore邻域、最短路径问题

shortest-path networkx python

Anathapindika · 技术社区 · 7 年前

我正试图在摩尔街区建立一个矩形图。在这里面,我在寻找最短的路径( 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()

1 回复 | 直到 7 年前

rodgdor 7 年前

这个奇怪的之字形是6条边的有效最短路径,我看不出有什么问题。另一方面,如果我们考虑到边缘。在这种情况下,您必须使用:

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

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

为您提供以下路径: