title: Find shortest path to one of many nodes with attribute
body: <p>I have a networkx graph representing the minimum spanning tree of roughly 1 million objects (vertices). I am wondering if there is an efficient way to find the shortest path between a given vertex and one of many other vertices.</p>
  
  <p>Here is an example graph with a smaller number of vertices (110)</p>
  
  <pre><code>nodes = [(0.0, {'label': 2}) ,
           (1.0, {'label': 2}) ,
           (2.0, {'label': 0}) ,
           (3.0, {'label': 2}) ,
           (4.0, {'label': 2}) ,
           (5.0, {'label': 0}) ,
           (6.0, {'label': 0}) ,
           (7.0, {'label': 2}) ,
           (8.0, {'label': 2}) ,
           (9.0, {'label': 1}) ,
           (10.0, {'label': 0}) ,
           (11.0, {'label': 1}) ,
           (12.0, {'label': 1}) ,
           (13.0, {'label': 0}) ,
           (14.0, {'label': 1}) ,
           (15.0, {'label': 2}) ,
           (16.0, {'label': 1}) ,
           (17.0, {'label': 1}) ,
           (18.0, {'label': 2}) ,
           (19.0, {'label': 2}) ,
           (20.0, {'label': 0}) ,
           (21.0, {'label': 1}) ,
           (22.0, {'label': 1}) ,
           (23.0, {'label': 0}) ,
           (24.0, {'label': 1}) ,
           (25.0, {'label': 2}) ,
           (26.0, {'label': 0}) ,
           (27.0, {'label': 0}) ,
           (28.0, {'label': 1}) ,
           (29.0, {'label': 0}) ,
           (30.0, {'label': 2}) ,
           (31.0, {'label': 1}) ,
           (32.0, {'label': 2}) ,
           (33.0, {'label': 1}) ,
           (34.0, {'label': 1}) ,
           (35.0, {'label': 1}) ,
           (36.0, {'label': 1}) ,
           (37.0, {'label': 2}) ,
           (38.0, {'label': 0}) ,
           (39.0, {'label': 0}) ,
           (40.0, {'label': 2}) ,
           (41.0, {'label': 0}) ,
           (42.0, {'label': 1}) ,
           (43.0, {'label': 0}) ,
           (44.0, {'label': 0}) ,
           (45.0, {'label': 2}) ,
           (46.0, {'label': 0}) ,
           (47.0, {'label': 2}) ,
           (48.0, {'label': 0}) ,
           (49.0, {'label': 1}) ,
           (50.0, {'label': 0}) ,
           (51.0, {'label': 1}) ,
           (52.0, {'label': 2}) ,
           (53.0, {'label': 0}) ,
           (54.0, {'label': 1}) ,
           (55.0, {'label': 1}) ,
           (56.0, {'label': 2}) ,
           (57.0, {'label': 1}) ,
           (58.0, {'label': 1}) ,
           (59.0, {'label': 0}) ,
           (60.0, {'label': 2}) ,
           (61.0, {'label': 1}) ,
           (62.0, {'label': 1}) ,
           (63.0, {'label': 2}) ,
           (64.0, {'label': 0}) ,
           (65.0, {'label': 0}) ,
           (66.0, {'label': 0}) ,
           (67.0, {'label': 0}) ,
           (68.0, {'label': 1}) ,
           (69.0, {'label': 2}) ,
           (70.0, {'label': 0}) ,
           (71.0, {'label': 1}) ,
           (72.0, {'label': 0}) ,
           (73.0, {'label': 2}) ,
           (74.0, {'label': 0}) ,
           (75.0, {'label': 1}) ,
           (76.0, {'label': 1}) ,
           (77.0, {'label': 0}) ,
           (78.0, {'label': 2}) ,
           (79.0, {'label': 2}) ,
           (80.0, {'label': 2}) ,
           (81.0, {'label': 1}) ,
           (82.0, {'label': 2}) ,
           (83.0, {'label': 2}) ,
           (84.0, {'label': 1}) ,
           (85.0, {'label': 0}) ,
           (86.0, {'label': 1}) ,
           (87.0, {'label': 2}) ,
           (88.0, {'label': 1}) ,
           (89.0, {'label': 0}) ,
           (90.0, {'label': 0}) ,
           (91.0, {'label': 2}) ,
           (92.0, {'label': 0}) ,
           (93.0, {'label': 1}) ,
           (94.0, {'label': 1}) ,
           (95.0, {'label': 2}) ,
           (96.0, {'label': 2}) ,
           (97.0, {'label': 0}) ,
           (98.0, {'label': 2}) ,
           (99.0, {'label': 2}) ,
           (100.0, {'label': -1}) ,
           (101.0, {'label': -1}) ,
           (102.0, {'label': 1}) ,
           (103.0, {'label': -1}) ,
           (104.0, {'label': -1}) ,
           (105.0, {'label': -1}) ,
           (106.0, {'label': -1}) ,
           (107.0, {'label': 1}) ,
           (108.0, {'label': 0}) ,
           (109.0, {'label': -1})]
  edges = [(0.0, 25.0, {'weight': 1.3788141613435239}) ,
           (0.0, 15.0, {'weight': 1.1948288781935414}) ,
           (1.0, 99.0, {'weight': 2.1024875417678257}) ,
           (1.0, 52.0, {'weight': 1.5298566582843918}) ,
           (2.0, 59.0, {'weight': 1.2222170767316791}) ,
           (3.0, 96.0, {'weight': 0.77235026806254947}) ,
           (3.0, 98.0, {'weight': 0.75540026318653475}) ,
           (3.0, 83.0, {'weight': 0.63745598060956865}) ,
           (4.0, 8.0, {'weight': 1.1460983565815646}) ,
           (5.0, 39.0, {'weight': 0.57882005244148982}) ,
           (6.0, 27.0, {'weight': 0.77903808587705414}) ,
           (6.0, 38.0, {'weight': 0.87763345274858739}) ,
           (7.0, 83.0, {'weight': 1.0592473391743824}) ,
           (7.0, 52.0, {'weight': 1.1650063193499598}) ,
           (8.0, 18.0, {'weight': 0.62985157194068553}) ,
           (8.0, 63.0, {'weight': 0.66061808561292024}) ,
           (9.0, 57.0, {'weight': 0.73138423240527128}) ,
           (9.0, 14.0, {'weight': 0.68690071596776681}) ,
           (10.0, 43.0, {'weight': 1.0938913337235003}) ,
           (11.0, 76.0, {'weight': 1.8066534138474315}) ,
           (11.0, 22.0, {'weight': 1.5814274601380762}) ,
           (12.0, 68.0, {'weight': 0.82964162447510292}) ,
           (12.0, 28.0, {'weight': 0.56687613489965616}) ,
           (13.0, 41.0, {'weight': 0.67883257822079479}) ,
           (13.0, 70.0, {'weight': 0.69594526555853065}) ,
           (13.0, 39.0, {'weight': 0.62690609201673064}) ,
           (14.0, 42.0, {'weight': 0.51384098628821639}) ,
           (15.0, 91.0, {'weight': 0.80363040334950342}) ,
           (15.0, 63.0, {'weight': 0.74055429404201112}) ,
           (16.0, 75.0, {'weight': 0.89225782872169068}) ,
           (16.0, 36.0, {'weight': 0.97796463842832249}) ,
           (16.0, 61.0, {'weight': 1.2426060084547763}) ,
           (17.0, 24.0, {'weight': 0.48569989925661516}) ,
           (17.0, 88.0, {'weight': 0.58411688395739225}) ,
           (17.0, 42.0, {'weight': 0.48569989925661516}) ,
           (18.0, 19.0, {'weight': 0.73750301595928458}) ,
           (18.0, 87.0, {'weight': 0.62985157194068553}) ,
           (19.0, 80.0, {'weight': 0.77740196142918039}) ,
           (20.0, 53.0, {'weight': 1.5817584651620507}) ,
           (21.0, 33.0, {'weight': 1.558483049272277}) ,
           (21.0, 35.0, {'weight': 1.022218339608882}) ,
           (22.0, 93.0, {'weight': 1.4628634684132413}) ,
           (22.0, 101.0, {'weight': 7.494583622053641}) ,
           (23.0, 97.0, {'weight': 0.86085201141197409}) ,
           (23.0, 90.0, {'weight': 1.4629842172999594}) ,
           (23.0, 65.0, {'weight': 0.94746570241498318}) ,
           (24.0, 34.0, {'weight': 0.55323853417352553}) ,
           (25.0, 104.0, {'weight': 4.9839694794161371}) ,
           (26.0, 85.0, {'weight': 1.5024751933287497}) ,
           (26.0, 46.0, {'weight': 1.2053565344116006}) ,
           (27.0, 72.0, {'weight': 0.72860577250944303}) ,
           (27.0, 92.0, {'weight': 0.74002007166874428}) ,
           (28.0, 54.0, {'weight': 0.55323853417352553}) ,
           (29.0, 50.0, {'weight': 0.81426784351619774}) ,
           (30.0, 98.0, {'weight': 0.77235026806254947}) ,
           (30.0, 78.0, {'weight': 0.79413937142096647}) ,
           (30.0, 95.0, {'weight': 0.78901093530213129}) ,
           (31.0, 68.0, {'weight': 0.98851671776185412}) ,
           (32.0, 95.0, {'weight': 0.8579399666494596}) ,
           (34.0, 54.0, {'weight': 0.55323853417352553}) ,
           (34.0, 55.0, {'weight': 0.60906522381767525}) ,
           (35.0, 62.0, {'weight': 0.66697239833732958}) ,
           (36.0, 93.0, {'weight': 1.2932994772208264}) ,
           (37.0, 80.0, {'weight': 0.85527462610640648}) ,
           (37.0, 96.0, {'weight': 0.85527462610640648}) ,
           (38.0, 46.0, {'weight': 0.95334944284759993}) ,
           (39.0, 50.0, {'weight': 0.52028039541706872}) ,
           (40.0, 69.0, {'weight': 1.7931323073700682}) ,
           (42.0, 62.0, {'weight': 0.51384098628821639}) ,
           (42.0, 81.0, {'weight': 0.5466147583189902}) ,
           (43.0, 65.0, {'weight': 1.0581157274507453}) ,
           (44.0, 108.0, {'weight': 3.0598509599260266}) ,
           (44.0, 70.0, {'weight': 1.0805691635112824}) ,
           (45.0, 56.0, {'weight': 1.3420236519319457}) ,
           (45.0, 79.0, {'weight': 1.6201017824952586}) ,
           (46.0, 53.0, {'weight': 1.070516213146298}) ,
           (47.0, 78.0, {'weight': 1.2822937333699174}) ,
           (47.0, 103.0, {'weight': 3.9053251231648707}) ,
           (48.0, 97.0, {'weight': 0.86085201141197409}) ,
           (48.0, 67.0, {'weight': 0.75656062694199944}) ,
           (49.0, 94.0, {'weight': 1.6216528905308547}) ,
           (49.0, 86.0, {'weight': 0.80157999082131093}) ,
           (49.0, 62.0, {'weight': 0.7081136236724922}) ,
           (51.0, 102.0, {'weight': 1.4704389417937378}) ,
           (51.0, 71.0, {'weight': 0.83506431983724716}) ,
           (54.0, 75.0, {'weight': 0.70074754481170742}) ,
           (55.0, 58.0, {'weight': 0.78571631647476448}) ,
           (56.0, 82.0, {'weight': 1.3387438494166808}) ,
           (57.0, 84.0, {'weight': 1.558483049272277}) ,
           (59.0, 64.0, {'weight': 1.0416266944398496}) ,
           (60.0, 98.0, {'weight': 1.2534403896544031}) ,
           (63.0, 73.0, {'weight': 0.83646303763566465}) ,
           (64.0, 72.0, {'weight': 0.8620326535711742}) ,
           (66.0, 77.0, {'weight': 0.79981721989351606}) ,
           (67.0, 72.0, {'weight': 0.74002007166874428}) ,
           (69.0, 83.0, {'weight': 1.5000235782351021}) ,
           (70.0, 77.0, {'weight': 0.75999034076724692}) ,
           (71.0, 88.0, {'weight': 0.66450874893016454}) ,
           (74.0, 97.0, {'weight': 0.8743417572549379}) ,
           (76.0, 107.0, {'weight': 2.0300278349030831}) ,
           (77.0, 89.0, {'weight': 0.75999034076724692}) ,
           (79.0, 106.0, {'weight': 4.5661761296968333}) ,
           (82.0, 95.0, {'weight': 1.083633962514291}) ,
           (84.0, 99.0, {'weight': 2.1024875417678257}) ,
           (89.0, 92.0, {'weight': 0.75419548272456249}) ,
           (100.0, 107.0, {'weight': 2.9259491743365307}) ,
           (101.0, 109.0, {'weight': 7.6747981730730297}) ,
           (102.0, 108.0, {'weight': 4.3128725576385092}) ,
           (104.0, 105.0, {'weight': 7.5515191839631273})]
  G2 = nx.Graph()
  G2.add_nodes_from(nodes)
  G2.add_edges_from(edges)
  </code></pre>
  
  <p>What I want is "which vertex that has label >= 0 is closest to each of the vertices with label = -1". With a small graph like this, the brute force approach using something like <code>nx.all_pairs_dijkstra_path_length()</code> and then checking the labels works fine, but it doesn't scale to very large graphs. Are there more efficient algorithms, especially if built-in to networkx, that I could use?</p>
  
  <p>UPDATE:</p>
  
  <p>I used the excellent suggestion by Richard and the comment below to write this. What I actually want is an array of labels, which I think made things less messy than Richard alluded to in networkx. The whole relabeling took 45 seconds on a dataset that took an hour to do by brute force!</p>
  
  <pre><code>def relabel(G, indices_to_relabel):
      """ 
      Update the anomaly labels to be the closest cluster.
      """
      # Add a "special" node that has zero weight to all the cluster nodes
      print('Adding special node')
      G.add_node('special', {'label': 'special'})
      special_edges = [(n, 'special', {'weight': 0}) 
                       for n, ndat in G.nodes_iter(data=True) 
                       if ndat['label'] != 'special' and ndat['label'] &gt;= 0]
      G.add_edges_from(special_edges)
  
      print('Calculating path from special node to all other nodes')
      paths = nx.shortest_path(G, source='special', target=None, weight='weight')
  
      print('Updating labels')
      new_labels = np.array([ndat['label'] for _, ndat in G.nodes_iter(data=True)])
      new_labels[indices_to_relabel] = [G.node[paths[n][1]]['label'] for n in indices_to_relabel]
  
      # Clean up
      G.remove_node('special')
      return new_labels
  </code></pre>