Welches Python-Paket implementiert den Bellman-Ford-Algorithmus für den kürzesten Pfad?

Question

Welches Python-Paket implementiert den Bellman-Ford-Algorithmus für den kürzesten Weg?

Gegeben ein Startknoten i und eine Adjazenzmatrix G mit negativen Wertigkeiten Ich möchte den kürzesten Weg von i zu einem anderen Knoten j finden. Z.B. mein Graph wie folgt aussieht:

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

kann ich nur eine all-pairs shortest path Umsetzung finden, die zu verschwenderisch scheint für meine Bedürfnisse angesichts meiner Graph groß ist und ich brauche nur den kürzesten Weg für 1 Paar von Knoten. Leistung wird für mich wichtig sein, vorausgesetzt, ich werde es für Tausende von Graphen verwenden.

Daher suche ich nach einer Bellman-Ford-Implementierung - hat jemand einen gesehen?

Answer 1

meine eigene

Rolled

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