def dijkstra(graph, start, end=None):
 D = {}
 P = {}
 Q = _priorityDictionary()
 Q[start] = 0
 for v in Q:
  D[v] = Q[v]
  if (v == end):
   break
  for w in graph.out_nbrs(v):
   edge_id = graph.edge_by_node(v, w)
   vwLength = (D[v] + graph.edge_data(edge_id))
   if (w in D):
    if (vwLength < D[w]):
     raise GraphError('Dijkstra: found better path to already-final vertex')
   elif ((w not in Q) or (vwLength < Q[w])):
    Q[w] = vwLength
    P[w] = v
 return (D, P)

def dijkstra ( graph , start , end = None ) : D = { } P = { } Q = _priorityDictionary ( ) Q [ start ] = 0 for v in Q : D [ v ] = Q [ v ] if ( v == end ) : break for w in graph . out_nbrs ( v ) : edge_id = graph . edge_by_node ( v , w ) vwLength = ( D [ v ] + graph . edge_data ( edge_id ) ) if ( w in D ) : if ( vwLength < D [ w ] ) : raise GraphError ( 'Dijkstra: found better path to already-final vertex' ) elif ( ( w not in Q ) or ( vwLength < Q [ w ] ) ) : Q [ w ] = vwLength P [ w ] = v return ( D , P )
dijkstras algorithm for shortest paths david eppstein .