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

Question

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

我的目标：对于网络中的每个节点，我想计算通过特定节点的最短路径的数量，并将该数字保存在 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

如果不进一步访问源代码，则无法确定，但我敢打赌：

S, P, sigma = _single_source_shortest_path_basic(G, s)

或

betweenness = _rescale(betweenness, len(G),...

重新缩放声音好像它将包含一个除法。

你试过用normalized=False调用这个函数吗？

Answer 2

我会尝试给出纯算法答案。

如果从v_1到v_2有几条最短路径，其中一些包含v_mid怎么办？如果这种情况对于每个 (v_1, v_2) 对都算作 1，则可以使用 Floyd-Warshall 算法。在它的运行之后，你有最短路径长度的矩阵。对于每个 u，遍历所有 (v_1, v_2) 对，如果 D[v_1, u] + D[u, v_2] == D[v_1, v_2]，则计数 +1。它是 O(n^3)，适用于密集图。

我不确定，但我认为可以对其进行调整以计算最短路径的数量。

Answer 3

我相信你可以修改Floyd-Warshall Algorithm以将路径的长度保存在另一个矩阵中。伪代码（基于维基百科）：

let dist and num be two |V| × |V| arrays of minimum
distances and lengths initialized to ∞ (infinity)

for each vertex v
   dist[v][v] ← 0
   num[v][v] ← 0

for each edge (u,v)
   dist[u][v] ← w(u,v)  // the weight of the edge (u,v)
   num[u][v] ← 1

for k from 1 to |V|
    for i from 1 to |V|
        for j from 1 to |V|
            if dist[i][j] > dist[i][k] + dist[k][j] 
                dist[i][j] ← dist[i][k] + dist[k][j]
                num[i][j] ← num[i][k] + num[k][j]
            end if

Answer 4

你可以直接使用 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 只有 returns 一条最短路径。在暴力搜索下面找到所有可能的最短路径。我不建议在大图中运行它：

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

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

Python: how to compute the number of shortest paths passing through one node?

python

shortest-path

networkx