réseaux, moore-neighbourhood, problème du plus court chemin

Question

J'essaie de construire un graphe rectangulaire dans un voisinage de Moore. A l'intérieur de celui-ci, je cherche le plus court chemin ( nx.shortest_path ) mais devient étrange (zig-zag) .

Je suis tout à fait sûr que la raison en est la façon dont je construis le graphique, mais je ne trouve pas le problème.

D'abord, je construis la grille et les nœuds :

#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

Ensuite, je calcule les bords et leurs poids.

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

à la recherche du chemin :

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

le traçage :

# 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

Cet étrange zigzag est un plus court chemin valide de 6 arêtes, je ne vois pas où est le problème. Par contre le zigzag n'est pas le plus court chemin si l'on prend en compte les poids des bords. Dans ce cas, vous devez utiliser :

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

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

Vous obtenez le chemin suivant :