Python:如何计算通过一个节点的最短路径数？

Question

假设我有一个 NxN 节点的常规网络。两个节点之间的最短路径是从一个源节点到达一个目标节点所需的最少跳数。现在，每条最短路径沿途都会经过多个节点。

我的目标:对于网络中的每个节点，我想计算通过特定节点的最短路径的数量，并将该数字保存在 dict 中。

在这个小例子中，节点 B 有 4 条最短路径通过它:A -> B，A -> C，C -> B，C -> A。 我希望能够为通用图中的每个节点计算这个数字。

我知道我可以使用 nx.betweenness_centrality() ，但这会给我一个分子(对于每个节点，我想要的)除以一个分母，该分母存储两个节点之间所有可能的最短路径。我什至访问了源代码，但我无法找出执行除法的位置。

我知道这是一个冗长的问题，但我没有其他方法可以解释我的问题。感谢任何愿意提供帮助的人。

编辑

这是 nx.betweenness_centrality() 的源代码。我的图是无向的。不清楚是哪一行托管了我上面介绍的部门:

def betweenness_centrality(G, k=None, normalized=True, weight=None,
                           endpoints=False,
                           seed=None): #G is the graph

    betweenness = dict.fromkeys(G, 0.0)  
    if k is None:
        nodes = G
    else:
        random.seed(seed)
        nodes = random.sample(G.nodes(), k)
    for s in nodes:
        # single source shortest paths
        if weight is None:  # use BFS
            S, P, sigma = _single_source_shortest_path_basic(G, s)
        else:  # use Dijkstra's algorithm
            S, P, sigma = _single_source_dijkstra_path_basic(G, s, weight)
        # accumulation
        if endpoints:
            betweenness = _accumulate_endpoints(betweenness, S, P, sigma, s)
        else:
            betweenness = _accumulate_basic(betweenness, S, P, sigma, s)
    # rescaling
    betweenness = _rescale(betweenness, len(G),
                           normalized=normalized,
                           directed=G.is_directed(),
                           k=k)
    return betweenness #Returns a dict with the node ID as a key and the value

Answer 1

你可以只使用nx.all_pairs_shortest_path(G):

>>> G = nx.Graph()
>>> G.add_path([0,1,2])

>>> spaths = nx.all_pairs_shortest_path(G)
>>> spaths
{0: {0: [0], 1: [0, 1], 2: [0, 1, 2]},
 1: {0: [1, 0], 1: [1], 2: [1, 2]},
 2: {0: [2, 1, 0], 1: [2, 1], 2: [2]}}

它会为您找到图中所有节点对之间的所有最短路径(这对于大型图来说非常昂贵)。然后，以下代码将为您提供所需的结果:

def num_spaths(G):
    n_spaths = dict.fromkeys(G, 0.0)
    spaths = nx.all_pairs_shortest_path(G)

    for source in G:
        for path in spaths[source].values():
            for node in path[1:]: # ignore firs element (source == node)
                n_spaths[node] += 1 # this path passes through `node`

    return n_spaths

在你的例子中:

>>> num_spaths(G)
{0: 2.0, 1: 4.0, 2: 2.0}

---

此外，如果您可以进入 all_pairs_shortest_path 代码并仔细编辑它以添加最短路径计数器和

for node in path[1:]:
    n_spaths[node] += 1

这样，您可以在找到一条路径的同时更新在线路径的数量，而不必在计算完所有路径后迭代所有路径(如我的代码所做的那样)。

编辑:in networkx (github) ，第 251 行说:

paths[w]=paths[v]+[w]

您可能会修改该函数以通过将 n_spath 作为参数传递给修改后的函数并在内部更新它来在线更新最短路径的数量(同时找到它们)。然后调用函数如下:

def num_spaths(G):
    n_spaths = dict.fromkeys(G, 0.0)
    for n in G:
        my_single_source_shortest_path(G, n, n_spaths)
    return n_spaths

和n_spaths 将更新最短路径的数量。

---

编辑:以上仅在 A 和 B 之间只有 1 条最短路径时有效，因为 nx.all_pairs_shortest_path 每个节点对仅返回一条最短路径。在暴力搜索下面找到所有可能的最短路径。我不建议在大图中运行它:

def bf_num_spaths(G):
    n_spaths = dict.fromkeys(G, 0.0)

    for source in G:
        for target in G:
            if source == target:
                continue
            for path in nx.all_shortest_paths(G, source, target):
                for node in path[1:]: # ignore firs element (source == node)
                    n_spaths[node] += 1 # this path passes through `node`

    return n_spaths