给定一个坐标列表，将值添加到这些坐标，直到最短路径列表发生变化

Question

所以我有一个问题，我希望你能指出正确的方向，完整的上下文问题，我有一个 3D numpy 数组，我用它来使用 Networkx 创建图形，并通过这些图形找到最短路径.我需要的是给定一组坐标，在这些坐标中添加“1”，直到最短路径列表发生变化（这只是一个例子，坐标列表可以有更多坐标），我的代码如下：

import numpy as np
import networkx as nx

arr = np.array([[[  0., 378.,  50., 174., 125.],
                 [  0.,   0.,   0.,   0.,   0.],
                 [  0., 154.,   0.,  20.,   0.],
                 [  0., 111.,  15.,   0.,  22.],
                 [  0.,  16.,   0.,  12.,   0.]],

                [[  0., 488.,  64.,  98., 117.],
                 [  0.,   0.,   0.,   0.,   0.],
                 [  0., 151.,   0.,  24.,   0.],
                 [  0.,  35.,  13.,   0.,  24.],
                 [  0.,  71.,   0.,  10.,   0.]],

                [[  0., 374., 110., 187., 189.],
                 [  0.,   0.,   0.,   0.,   0.],
                 [  0., 195.,   0.,  12.,   0.],
                 [  0.,  42.,  14.,   0.,  21.],
                 [  0.,  16.,   0.,  19.,   0.]]])

graphs = []
path = []

for i in arr:
    graphs.append(nx.from_numpy_array(i, create_using = nx.DiGraph)) #Create graphs from numpy array

for graph in graphs:
    path.append(nx.shortest_path(graph, 0, 1, weight = 'weight'))   #Find the shortest path

print(path) 

#path = [[0, 2, 3, 4, 1], [0, 2, 3, 1], [0, 2, 3, 4, 1]] #Shortest path for each array

coordinates = [[2, 3], [3, 4]] #List of coordinates in the array that I want to add 1

我想遍历我的坐标列表并添加 1 直到我的路径列表发生变化，例如

#My first coordinate is [2, 3] so I add 1 to these coordinates and calculate the shortest path again 
#to see if the path changes

arr[:, 2, 3] = arr[:, 2, 3] + 1     #Path = [[0, 2, 3, 4, 1], [0, 2, 3, 1], [0, 2, 3, 4, 1]]
arr[:, 2, 3] = arr[:, 2, 3] + 2     #Path = [[0, 2, 3, 4, 1], [0, 2, 3, 1], [0, 2, 3, 4, 1]]
...
arr[:, 2, 3] = arr[:, 2, 3] + 9     #Path = [[0, 2, 3, 4, 1], [0, 2, 3, 1], [0, 2, 3, 4, 1]]
arr[:, 2, 3] = arr[:, 2, 3] + 10    #Path = [[0, 2, 3, 4, 1], [0, 3, 1], [0, 2, 3, 4, 1]] #Here the path changes so I keep the 9

完成第一个坐标后，我将转到第二个。

#The second coordinate is [3, 4] so...

arr[:, 3, 4] = arr[:, 3, 4] + 1  #Path = [[0, 2, 3, 4, 1], [0, 2, 3, 1], [0, 2, 3, 4, 1]]
...
arr[:, 3, 4] = arr[:, 3, 4] + 4  #Path = [[0, 2, 3, 4, 1], [0, 2, 3, 1], [0, 2, 3, 4, 1]]
arr[:, 3, 4] = arr[:, 3, 4] + 5  #Path = [[0, 2, 3, 4, 1], [0, 2, 3, 1], [0, 2, 3, 1]] #Here the path changes so I keep the 4

我正在考虑使用类似 while (path == newpath) 的 while 循环，然后继续添加一个，但我不确定如何遍历坐标列表以及如何在找到更改的值后停止路径，所以任何帮助将不胜感激，谢谢！

Answer 1

你对循环结构的假设是正确的。只需确保正确复制数组即可。这是代码：

from copy import deepcopy

for x,y in coordinates:
    # Make deepcopies of path and arr
    # For the first iteration, set newpath = path
    new_path = deepcopy(path)
    temp_arr = deepcopy(arr)

    # Set counter for each coordinate to zero
    cnt = 0

    # Iterate till a change in path is observed
    while path == new_path:
        # Add 1 to x,y
        temp_arr[:, x, y] = temp_arr[:, x, y] + 1

        # Increment the counter
        cnt += 1

        # Reconstruct the graph and shortest path
        temp_graph = []
        new_path = []
        for i in temp_arr:
            temp_graph.append(nx.from_numpy_array(i, create_using = nx.DiGraph))

        for graph in temp_graph:
            new_path.append(nx.shortest_path(graph, 0, 1, weight = 'weight'))

    # If we are out of the loop, this means that
    # the shortest path has changed. Print the details.
    print("For coordinates X={} and Y={} the change is at {}".format(x, y, cnt))

对于工作版本，您可以查看 this notebook。

此外，我不确定您是否总是想找出 source=0 和 target=1 之间的最短路径，但您可以根据需要更改值。您可以查看文档 here.

参考文献:

Deepcopy Python List

给定一个坐标列表，将值添加到这些坐标，直到最短路径列表发生变化

Given a list of coordinates add values to those coordinates until shortest path list changes

python

for-loop

while-loop

networkx