title: Python: how to optimize the count of all possible shortest paths?
body: <p>In a <code>3x3</code> 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.</p>
  
  <p>This requires using the <code>nx.all_shortest_paths(G,source,target)</code> function, which returns a <code>generator</code>. This is at variance from using the <code>nx.all_pairs_shortest_path(G)</code>, as suggested <a href="https://stackoverflow.com/questions/36552135/python-how-to-compute-the-number-of-shortest-paths-passing-through-one-node?answertab=active#tab-top">here</a>. The difference is that in the former case the function computes <strong>all</strong> the shortest paths between any two nodes, while in the latter case it computes <strong>only one</strong> shortest path between the same pair of nodes. </p>
  
  <p>Given that I need to consider <strong>all</strong> shortest paths, I have come up with the following script. This is how I generate the network I am working with:</p>
  
  <pre><code>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)
  </code></pre>
  
  <p>And this is how I print all the shortest paths between any two nodes:</p>
  
  <pre><code>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('------')
  </code></pre>
  
  <p>The result is a path from node <code>x</code> to node <code>y</code> which only includes the nodes along the way. An excerpt of what I get is:</p>
  
  <pre><code>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...
  </code></pre>
  
  <p><strong>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?</strong> 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.</p>