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

Question

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

Вывод не учитывает тип возврата; вы можете, однако, попытаться разделить дженерики; например, вы могли бы написать код, чтобы разрешить:

.Cast().To<Type2>()

, имея (непроверенный, только указательный)

public static CastHelper<T> Cast<T>(this T obj) {
    return new CastHelper<T>(obj);
}
public struct CastHelper<TFrom> {
    private readonly TFrom obj;
    public CastHelper(TFrom obj) { this.obj = obj;}
    public TTo To<TTo>() {
       // your code here
    }
}

0

python networkx

задан W3LS 1 March 2019 в 03:14

2 ответа

Другие вопросы по тегам:

python networkx

Похожие вопросы:

score 0 · Answer 1

Кажется, работает алгоритм bellman_ford_predecessor_and_distance. Если расстояние < = -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)

score 0 · Answer 2

Я не нашел никакого специального алгоритма в 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]