哪个python包实现了Bellman-Ford最短路径算法？ [关闭]-Java 学习之路

-1

哪个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对节点的最短路径 . 性能对我来说很重要，因为我会将它用于数千个图表 .

因此，我正在四处寻找贝尔曼 - 福特的实施 - 有人见过吗？

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

回复于 2024-04-28T19:56:40+08:00

哪个python包实现了Bellman-Ford最短路径算法？ [关闭]

1 回答

相关问题