title: Python Dijkstra k shortest paths
body: <p>I'm trying to make a small public transport routing application.</p>
  
  <p>My data is represented in a following structure:</p>
  
  <pre><code>graph = {'A': {'B':3, 'C':5},
       'B': {'C':2, 'D':2},
       'C': {'D':1},
       'D': {'C':3},
       'E': {'F':8},
       'F': {'C':2}}
  </code></pre>
  
  <p>Where:</p>
  
  <ol>
  <li>graph dict key is a node</li>
  <li>subdict key is an edge between 2 nodes</li>
  <li>subdict value is an edge weight</li>
  </ol>
  
  <p>I was using find_shortest_path algorithm described here <a href="https://www.python.org/doc/essays/graphs/" rel="noreferrer">https://www.python.org/doc/essays/graphs/</a> but it is rather slow because of recursion and has no support of weights.</p>
  
  <p>So I moved to the algorithm described by Davide Epstein here <a href="http://code.activestate.com/recipes/119466-dijkstras-algorithm-for-shortest-paths/" rel="noreferrer">http://code.activestate.com/recipes/119466-dijkstras-algorithm-for-shortest-paths/</a> (and even better implementation could be find there in comments with the usage of heapq)</p>
  
  <p>It works great, it is really fast, but I get only the best route instead of the list of all possible routes. And that is where I stuck.</p>
  
  <p>Could somebody help me with that please, or at least give a direction? I'm not very good in graph shortest paths algorithms. </p>
  
  <p>Thanks in advance!</p>