Python:如何计算通过一个节点的最短路径数? [英] Python: how to compute the number of shortest paths passing through one node?

问题描述

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

Say that I have a regular network of NxN nodes. The shortest path between two nodes is the minimum number of hops required to reach one target node from a source node. Now, each shortest path passes through a number of nodes along the way.

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

My goal: for each node in the network, I want to count the number of shortest paths that pass through a specific node, and save that number in a dict.

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

In this little example, node B has 4 shortest paths passing through it: A -> B, A -> C, C -> B, C -> A. I want to be able to compute this number for each node in a generic graph.

我知道我可以使用 nx.betweenness_centrality()，但这将为我提供一个分子(对于每个节点，我想要的)除以分母，该分母存储两个节点之间所有可能的最短路径.我什至已经访问了源代码，但无法弄清楚执行除法的地方.

I know I could use the nx.betweenness_centrality(), but this will give me a numerator (which is, for each node, what I want) divided by a denominator which stores all the possible shortest paths between two nodes. I have even accessed the source code but I wasn't able to figure out where the division is performed.

我知道这是一个罗word的问题，但是我没有其他方法可以解释我的问题.谢谢任何能为您提供帮助的人.

I know this is a wordy question but I had no other means to explain my problem. Thank you to anyone who will help.

编辑

这是nx.betweenness_centrality()的源代码.我的图是无向的.目前尚不清楚我在上面介绍的部门是哪一行:

This is the source code for nx.betweenness_centrality(). My graph is undirected. It is unclear which line hosts the division I introduced above:

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

推荐答案

您可以只使用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]}}

哪个可以找到图形中所有节点对之间的所有最短路径(对于大型图形而言，这是非常昂贵的).然后，以下代码为您提供所需的结果:

Which finds you all the shortest paths between all pair of nodes in a graph (which is very expensive for large graphs). Then, the following code gives you the desired result:

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代码并对其进行直观的编辑，以添加用于最短路径的计数器，并且

---

Additionally, if you could go inside the all_pairs_shortest_path code and sightly edit it to add a counter for shortest paths and

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

这样，您将在找到一个路径的同时更新在线路径的数量，而不必在计算所有路径后遍历所有路径(就像我的代码一样).

this way, you would update the number of paths online at the same time you find one, rather than having to iterate over all them (as my code does) after all them are calculated.

在networkx(github)，第251行说:

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

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

You could potentially modify that function to update the number of shortest paths online (at the same time they are found) by passing n_spath as an argument to the modified function and updating it inside. Then calling the function would be as:

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之间只有最短路径的情况下有效，因为nx.all_pairs_shortest_path每个节点对仅返回一条最短路径.在下面找到蛮力搜索所有可能的最短路径.我不建议在大图中运行它:

The above only works if there is only 1 shortest path between A and B, as nx.all_pairs_shortest_path only returns one shortest paths per each node pair. Find bellow the brute force search for all posible shortest paths. I wouldn't recommend runing this in a large graph:

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:如何计算通过一个节点的最短路径数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！