哪個python包實現了Bellman-Ford最短路徑算法？

Question

哪個python包實現了Bellman-Ford最短路徑算法？

給定一個起始節點i和一個負權重的鄰接矩陣G，我想找到從i到另一個節點j的最短路徑。例如。我圖的樣子：

import numpy 
G = numpy.array([[ 0. , 0.55, 1.22], 
       [-0.54, 0. , 0.63], 
       [-1.3 , -0.63, 0. ]]) 

我只能找到一個all-pairs shortest path實施給予我的需要我的圖是大，我只需要1對節點的最短路徑，這似乎太浪費了。由於我將使用它來處理數千個圖表，因此性能對我來說很重要。

因此，我正在四處尋找一個貝爾曼 - 福特實施 - 有誰見過嗎？

Answer 1

滾我自己

def bellmanFord(source, weights): 
    ''' 
    This implementation takes in a graph and fills two arrays 
    (distance and predecessor) with shortest-path (less cost/distance/metric) information 

    https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm 
    ''' 
    n = weights.shape[0] 

    # Step 1: initialize graph 
    distance = np.empty(n) 
    distance.fill(float('Inf'))  # At the beginning, all vertices have a weight of infinity 
    predecessor = np.empty(n) 
    predecessor.fill(float('NaN')) # And a null predecessor 

    distance[source] = 0    # Except for the Source, where the Weight is zero 

    # Step 2: relax edges repeatedly 
    for _ in xrange(1, n): 
     for (u, v), w in np.ndenumerate(weights): 
     if distance[u] + w < distance[v]: 
     distance[v] = distance[u] + w 
    predecessor[v] = u 

    # Step 3: check 
    for negative - weight cycles 
    for (u, v), w in np.ndenumerate(weights): 
     if distance[u] + w < distance[v]: 
     raise ValueError("Graph contains a negative-weight cycle") 

    return distance, predecessor