title: Python : Dijkstra between two points in sparse metric graph
body: <p>I am dealing with very large (but sparse) metric graph <code>G</code>, with say <code>N = 20000</code> vertices but not so many edges, allowing to store (using <code>scipy.sparse.matrix</code> class) the corresponding <code>N x N</code> weight matrix.</p>
  
  <p>I would be interested in the shortest path length matrix (distance on the graph), but I can't store the <code>N x N</code> distance matrix (which won't be sparse anymore). Therefore, I selected a small number <code>k</code> of vertices, and I would be interested into computing the <code>k x k</code> pairwise shortest path distances between these vertices.</p>
  
  <p>The function <code>scipy.sparse.csgraph.dijkstra</code> (<a href="https://docs.scipy.org/doc/scipy-0.14.0/reference/generated/scipy.sparse.csgraph.dijkstra.html" rel="nofollow noreferrer">https://docs.scipy.org/doc/scipy-0.14.0/reference/generated/scipy.sparse.csgraph.dijkstra.html</a>) might be adapted (with the argument <code>indices</code>) but it computes the distances between points to all the vertices on the graph - so a <code>k x N</code> matrix. Along with the overkill in running time, it could lead to memory issus as well.</p>
  
  <p>Basically I would be ok to call a function <code>dijkstra(G, i, j)</code> that will give me the shortest path length between vertices i and j in the graph <code>G</code>. I know I can implement it by myself, but I would prefer to rely on an optimized version of it, and it would seem crazy to me that this is not implemented in some standard Python library (numpy, scipy...). </p>
  
  <p>PS : Additionally, if you know a Python library that take advantage of knowing that the <code>G</code> is a metric graph, and thus for example the shortest path between two connected vertices is the weight of the corresponding edge, etc. it would be very informative :-)</p>
  
  <p>PS2 : Note that I don't need the shortest paths. Only shortest path length.</p>
  
  <p>PS3 : To fix idea, these graphs are built from triangulated 3D shapes. This is why these are sparse metric graphs.</p>