title: Lowest common ancestor in python's NetworkX
body: <p>Using NetworkX</p>
  
  <p>I want to get lowest common ancestor from node1 and node11 in DiGraph.</p>
  
  <p>The following is the code.</p>
  
  <pre><code>import networkx as nx
  
  G = nx.DiGraph() #Directed graph
  G.add_nodes_from([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15])
  G.add_edges_from([(2,1),(3,1),(4,1),(5,2),(6,2),(7,3),(8,3),(9,3),(10,4),(10,12),(14,9),(15,8),(12,11),(13,11),(14,12),(15,13)])
  
  ancestors1 = nx.ancestors(G, 1)
  ancestors2 = nx.ancestors(G, 11)
  
  src_set = set(ancestors1)
  tag_set = set(ancestors2)
  matched_list = list(src_set &amp; tag_set)
  
  dic = {}
  
  for elem in matched_list:
      print elem
      length1 = nx.dijkstra_path_length(G, elem, 1)
      path1 = nx.dijkstra_path(G, elem, 1)
      dist1 = len(path1)
      length2 = nx.dijkstra_path_length(G, elem, 11)
      path2 = nx.dijkstra_path(G, elem, 11)
      dist2 = len(path2)
      dist_sum = dist1 + dist2
      dic[elem] = dist_sum
  
  min_num = min(dic.values()) 
  for k, v in sorted(dic.items(), key=lambda x:x[1]):
      if v != min_num:
          break
      else:
          print k, v
  </code></pre>
  
  <p>I have a problem with a execution speed, so I want faster execution speed.</p>
  
  <p>If you have any good idea or algorithm, please tell me the idea.</p>
  
  <p>Sorry for the poor English.</p>