python之将矢量化与 numpy 结合用于 Bellman-Ford 算法

我一直在努力编写 Bellman Ford 算法来寻找图中的最短路径，虽然我有一个可行的解决方案，但它运行得不是很快，我被引导相信它可能是如果我使用 numpy 而不是我当前的方法，速度会更快。

这是我使用 for 循环的解决方案:

import os                     
file = open(os.path.dirname(os.path.realpath(__file__)) + "/g_small.txt") 
 
vertices, edges = map(lambda x: int(x), file.readline().replace("\n", "").split(" ")) 
 
adjacency_list = [[] for k in xrange(vertices)] 
for line in file.readlines(): 
    tail, head, weight = line.split(" ") 
    adjacency_list[int(head)-1].append({"from" : int(tail), "weight" : int(weight)}) 
 
n = vertices 
 
shortest_paths = [] 
s=2 
 
cache = [[0 for k in xrange(vertices)] for j in xrange(vertices)] 
cache[0][s] = 0 
 
for v in range(0, vertices): 
    if v != s: 
    cache[0][v] = float("inf") 
 
# this can be done with numpy I think? 
for i in range(1, vertices): 
    for v in range(0, vertices): 
        adjacent_nodes = adjacency_list[v] 
 
        least_adjacent_cost = float("inf") 
        for node in adjacent_nodes: 
            adjacent_cost = cache[i-1][node["from"]-1] + node["weight"] 
            if adjacent_cost < least_adjacent_cost: 
                least_adjacent_cost = adjacent_cost 
 
        cache[i][v] = min(cache[i-1][v], least_adjacent_cost) 
 
shortest_paths.append([s, cache[vertices-1]]) 
 
for path in shortest_paths: 
    print(str(path[1])) 
 
shortest_path = min(reduce(lambda x, y: x + y, map(lambda x: x[1], shortest_paths)))   
print("Shortest Path: " + str(shortest_path))   

输入文件如下所示 -> https://github.com/mneedham/algorithms2/blob/master/shortestpath/g_small.txt

除了大约一半的嵌套循环外，它几乎没有什么意思。我尝试使用 numpy 对其进行矢量化，但我不太确定该怎么做，因为矩阵/二维数组在每次迭代时都会发生变化。

如果有人对我需要做什么有任何想法，甚至可以阅读一些可以帮助我前进的东西，那就太棒了。

==================

我写了一个更新版本以考虑 Jaime 的评论:

s=0 
 
def initialise_cache(vertices, s): 
    cache = [0 for k in xrange(vertices)] 
    cache[s] = 0 
 
    for v in range(0, vertices): 
        if v != s: 
            cache[v] = float("inf") 
    return cache     
 
cache = initialise_cache(vertices, s) 
 
for i in range(1, vertices): 
    previous_cache = deepcopy(cache) 
    cache = initialise_cache(vertices, s) 
    for v in range(0, vertices): 
        adjacent_nodes = adjacency_list[v] 
 
    least_adjacent_cost = float("inf") 
    for node in adjacent_nodes: 
        adjacent_cost = previous_cache[node["from"]-1] + node["weight"] 
        if adjacent_cost < least_adjacent_cost: 
            least_adjacent_cost = adjacent_cost 
 
    cache[v] = min(previous_cache[v], least_adjacent_cost) 

================

这次使用矢量化的另一个新版本:

def initialise_cache(vertices, s): 
    cache = empty(vertices) 
    cache[:] = float("inf") 
    cache[s] = 0 
    return cache     
 
adjacency_matrix = zeros((vertices, vertices)) 
adjacency_matrix[:] = float("inf") 
for line in file.readlines(): 
    tail, head, weight = line.split(" ") 
    adjacency_matrix[int(head)-1][int(tail)-1] = int(weight)     
 
n = vertices 
shortest_paths = [] 
s=2 
 
cache = initialise_cache(vertices, s) 
for i in range(1, vertices): 
    previous_cache = cache 
    combined = (previous_cache.T + adjacency_matrix).min(axis=1) 
    cache = minimum(previous_cache, combined) 
 
shortest_paths.append([s, cache]) 

请您参考如下方法:

在听从 Jaime 的建议后，我得到了以下矢量化代码:

def initialise_cache(vertices, s): 
    cache = empty(vertices) 
    cache[:] = float("inf") 
    cache[s] = 0 
    return cache     
 
adjacency_matrix = zeros((vertices, vertices)) 
adjacency_matrix[:] = float("inf") 
for line in file.readlines(): 
    tail, head, weight = line.split(" ") 
    adjacency_matrix[int(head)-1][int(tail)-1] = int(weight)     
 
n = vertices 
shortest_paths = [] 
s=2 
 
cache = initialise_cache(vertices, s) 
for i in range(1, vertices): 
    previous_cache = cache 
    combined = (previous_cache.T + adjacency_matrix).min(axis=1) 
    cache = minimum(previous_cache, combined) 
 
shortest_paths.append([s, cache])