在 NetworkX 图中指定边的深度

Question

我有一个无向图，我想在不知道 source 和 sink 的情况下找到最短路径。 NeworkX的all_pairs_dijkstra_path允许在不知道source和sink的情况下发现所有最短路径，只要给定一个长度cutoff（衡量遍历的深度）即可。

目前，遍历的每条边都会增加 +1 深度。有没有一种方法可以指定边缘属性

每条边都有一个权重w，据此评估路径长度（和最短路径）
每条边还携带一个深度d，指定的总深度终止路径搜索？

Answer 1

创建图形时，您需要为每条边指定一个代表距离的属性：

G.add_edge(0, 1, distance=0.4)

计算最短路径时，您可以指定该属性，以便计算加权最短路径：

paths = nx.shortest_path(G, weight='distance')

all_pairs_shortest_paths 只计算未加权的情况；但是，如果您不指定源节点和目标节点，shortest_path 也会计算所有对。

编辑

networkx 中没有任何符合要求的东西 (AFAIK)。但是，您可以使用 nx.simple_paths.shortest_simple_paths 为按总“深度”排序的两个节点之间的所有路径创建一个生成器，然后根据权重计算最短路径：

import itertools
import networkx as nx
import numpy as np

def path_cost(G, path, attr='weight'):
    return sum([G[path[i]][path[i+1]][attr] for i in range(len(path)-1)])

G = ...

cutoff = 3
output = dict()
for source, target in itertools.combinations(list(G.nodes), 2):
    minimum_cost = np.inf
    for path in nx.simple_paths.shortest_simple_paths(G, source, target, weight='depth'):
        if path_cost(G, path, 'depth') > cutoff:
            continue # to next source, target pair
        else:
            if path_cost(G, path, 'weight') < minimum_cost:
                output[(source, target)] = path

在 NetworkX 图中指定边的深度

Specify depth for edge in NetworkX graph

python

traversal

graph

networkx

编辑