Python：如何优化所有可能的最短路径的数量？ [英] Python: how to optimize the count of all possible shortest paths?
问题描述
在 3x3 网络中，我希望能够确定任何两个节点之间的所有最短路径。然后，对于网络中的每个节点，我想计算一个特定节点有多少最短路径。
这需要使用 nx。 all_shortest_paths（G，source，target）函数，它返回一个 generator 。这与使用 nx.all_pairs_shortest_path（G）不同，如此处。不同的是，在前一种情况下，函数计算任意两个节点之间的最短路径，而在后一种情况下，它计算同一对节点之间只有一个最短路径。节点。
鉴于我需要考虑所有最短路径，我已经提出了以下脚本。这是我如何生成我正在使用的网络：
导入networkx为nx
N = 3 $ b $ （）（）（）（）（）（）（）（）（）（）（）（） （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在G.nodes（）中：
for G.nodes ）：
if（n！= j）：＃排除自循环
gener = nx.all_shortest_paths（G，source = n，target = j）
print（'From node' + str（j）+'to'+ str（j））
for p in gener：
print（p）
print（'------'）
结果是一条路径节点 x 到节点 y ，它只包含沿途的节点。我得到的摘录是：
从节点0到2＃只有一条路径存在
[0，1 ，2]＃节点1从节点0到节点2传递
------
从节点0到4＃存在两条路径
[0，1，4 ] #Node 1从节点0到节点4传递
[0，3，4] #Node 3从节点0传递到节点4
------
...继续，直到所有节点对都被覆盖...
我的问题：我如何修改最后一个代码块，以确保我知道总共有多少最短路径通过每个节点？根据我提供的摘录结果，节点1通过2次，而节点3通过1次（排除开始和结束节点）。这个计算需要进行到最后，以确定通过每个节点的最终路径数量。 我会建议使每个节点的字典映射为0在G.nodes（）中为n的b
counts = {}
：counts [n] = 0
然后对于您找到的每条路径 - 您已经找到并打印它们全部 - 遍历路径上的顶点，递增字典中的适当值：
＃...
for p in gener：
print（p）
for v in p：counts [v] + = 1
In a 3x3 network I want to be able to determine all the shortest paths between any two nodes. Then, for each node in the network, I want to compute how many shortest paths pass through one specific node.
This requires using the nx.all_shortest_paths(G,source,target) function, which returns a generator. This is at variance from using the nx.all_pairs_shortest_path(G), as suggested here. The difference is that in the former case the function computes all the shortest paths between any two nodes, while in the latter case it computes only one shortest path between the same pair of nodes.
Given that I need to consider all shortest paths, I have come up with the following script. This is how I generate the network I am working with:
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)
And this is how I print all the shortest paths between any two nodes:
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('------')
The result is a path from node x to node y which only includes the nodes along the way. An excerpt of what I get is:
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...
My question: how could I amend the last code block to make sure that I know how many shortest paths, in total, pass through each node? According to the excerpt outcome I've provided, node 1 is passed through 2 times, while node 3 is passed through 1 time (starting and ending node are excluded). This calculation needs to be carried out to the end to figure out the final number of paths through each node.
I would suggest making a dict mapping each node to 0
counts = {}
for n in G.nodes(): counts[n] = 0
and then for each path you find -- you're already finding and printing them all -- iterate through the vertices on the path incrementing the appropriate values in your dict:
# ...
for p in gener:
print(p)
for v in p: counts[v] += 1
这篇关于Python：如何优化所有可能的最短路径的数量？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
