NetworkX加权有向图算法

Question

我正在尝试解决一个类似于我下面描述的问题。你能不能建议一个解决方案或推荐一些算法在NetworkX中试用。非常感谢。你知道吗

假设有一个球的起始动量为100。球在失去所有的动量和停止之前，能沿着所有可能的路径走多远？你知道吗

当球滚上坡时，它失去了动量（即边缘的重量为负）。你知道吗

当球滚下山时，它获得动量（即边缘有正重量）。你知道吗

示例：

第一条路径：（1）---[权重：-50]-->；（2）---[权重：40]-->；（3）---[权重：-50]-->；（4）---[权重：-90]-->；（5）

第二条路径：（1）--[重量：-105]-->；（6）

等等

因此，在第一条路径中，球只能到达节点4。在第二条路径中，球不会越过节点1。你知道吗

Answer 1

bellman\u ford\u的前身\u和\u距离算法似乎可以工作。如果距离<；=-100，那么球就停在前一个节点上，所以我复制了图，删除了相关的边，然后再次运行算法进行检查。你知道吗

import networkx as nx

G = nx.DiGraph()

G.add_edge(1, 2, weight= -50)
G.add_edge(2, 3, weight= 40)
G.add_edge(3, 4, weight= -50)
G.add_edge(4, 5, weight= -90)
G.add_edge(1, 6, weight= -105)
G.add_edge(6, 7, weight= 110)

pred, dist = nx.bellman_ford_predecessor_and_distance(G, 1)

print(pred, dist)

F = G

for x, y in dist.items():
 if y <= -100:
  z = pred.get(x)[0]
  F.remove_edge(z,x)  

pred, dist = nx.bellman_ford_predecessor_and_distance(G, 1)

print(pred, dist)

Answer 2

我还没有在Networkx中找到任何用于此目的的特殊算法。您可以使用以下函数，该函数使用Bellman-Ford算法：

import networkx as nx

G = nx.DiGraph()
G.add_weighted_edges_from([(1, 2, -50), (2, 3, 40), (3, 4, -50),
                           (4, 5, -90), (1, 6, -105)])

def func(graph, source, target, start_weight):
    total = start_weight
    path = []
    p = nx.bellman_ford_path(graph, source, target)
    for u, v in zip(p, p[1:]):
        total += G[u][v]['weight']
        path.append(u)
        if total < 0:
            return path
    else:
        return path

print(func(G, 1, 5, 100))
# [1, 2, 3, 4]

print(func(G, 1, 6, 100))
# [1]