在NetworkX图形中指定边的深度

Question

我有一个无向图，我想在不知道source和sink的情况下找到它的最短路径NeworkX的all_pairs_dijkstra_path允许在不知道源和汇的情况下发现所有最短路径，只要给定长度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