Python: 如何优化所有可能的最短路径的数量？

Question

在 3x3 网络中，我希望能够确定任意两个节点之间的所有最短路径。然后，对于网络中的每个节点，我想计算有多少条最短路径通过一个特定节点。

这需要使用 nx.all_shortest_paths(G,source,target) 函数，其中 returns 一个 generator。这与使用 nx.all_pairs_shortest_path(G) 的建议不同。不同之处在于，在前一种情况下，函数计算 all 任意两个节点之间的最短路径，而在后一种情况下，函数计算 only one shortest同一对节点之间的路径。

鉴于我需要考虑所有最短路径，我想出了以下脚本。这就是我生成正在使用的网络的方式：

import networkx as nx
N=3
G=nx.grid_2d_graph(N,N)
pos = dict( (n, n) for n in G.nodes() )
labels = dict( ((i, j), i + (N-1-j) * N ) for i, j in G.nodes() )
nx.relabel_nodes(G,labels,False)
inds=labels.keys()
vals=labels.values()
inds.sort()
vals.sort()
pos2=dict(zip(vals,inds))
nx.draw_networkx(G, pos=pos2, with_labels=False, node_size = 15)

这就是我打印任意两个节点之间所有最短路径的方式：

for n in G.nodes():
    for j in G.nodes():
        if (n!=j): #Self-loops are excluded
            gener=nx.all_shortest_paths(G,source=n,target=j)
            print('From node '+str(n)+' to '+str(j))
            for p in gener:
                print(p) 
            print('------')

结果是从节点 x 到节点 y 的路径，它只包括沿途的节点。我得到的摘录是：

From node 0 to 2 #Only one path exists
[0, 1, 2] #Node 1 is passed through while going from node 0 to node 2
------
From node 0 to 4 #Two paths exist
[0, 1, 4] #Node 1 is passed through while going from node 0 to node 4
[0, 3, 4] #Node 3 is passed through while going from node 0 to node 4
------
...continues until all pairs of nodes are covered...

我的问题：我如何修改最后一个代码块以确保我知道总共有多少条最短路径通过每个节点？根据摘录结果我已经提供了，节点 1 通过了 2 次，而节点 3 通过了 1 次（不包括开始和结束节点）。这个计算需要一直进行到最后，才能算出最终通过每个节点的路径数。

Answer 1

我建议将每个节点映射到 0

counts = {}
for n in G.nodes(): counts[n] = 0

然后对于您找到的每条路径——您已经找到并打印它们——遍历路径上的顶点，增加字典中的适当值：

# ...
for p in gener:
    print(p)
    for v in p: counts[v] += 1

Answer 2

您要计算的是未规范化的 betweenness centrality。

来自Wikipedia：

The betweenness centrality is an indicator of a node's centrality in a network. It is equal to the number of shortest paths from all vertices to all others that pass through that node.

更一般地说，我建议您查看所有 standard measures of centrality already in Networkx。

Python: 如何优化所有可能的最短路径的数量？

Python: how to optimize the count of all possible shortest paths?

python

graph

shortest-path

networkx

graph-algorithm