Сетевые алгоритмы взвешенного диграфа

Question

Я пытаюсь решить проблему, аналогичную описанной ниже.Не могли бы вы предложить решение или рекомендовать некоторые алгоритмы, чтобы попробовать в NetworkX.Большое спасибо.

Скажем, есть шар, у которого стартовый импульс равен 100. Как далеко шар может пройти по каждому из возможных путей, прежде чем он потеряет весь импульс и остановится?

Когда шарик катится в гору, он теряет импульс (т. Е. Ребро имеет отрицательный вес).

Когда шарик катится вниз, он набирает обороты (то есть ребро имеет положительный вес).

Примеры:

1-й путь: (1) - [вес: -50] -> (2) - [вес: 40] -> (3) - [вес: -50] ->(4) - [вес: -90] -> (5)

2-й путь: (1) - [вес: -105] -> (6)

и т. Д..

Таким образом, на первом пути мяч проходит только до узла 4. На втором пути мяч не проходит мимо узла 1.

Answer 1

Я не нашел специального алгоритма в Networkx для этой цели.Вы можете использовать следующую функцию, которая использует алгоритм Беллмана-Форда:

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]

Answer 2

Кажется, работает алгоритм bellman_ford_predecessor_and_distance.Если расстояние <= -100, то шар остановился на узле-предшественнике, поэтому я скопировал график, удалил соответствующие ребра и снова запустил алгоритм для проверки. </p>

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)