algorithm - Optimal Directed Dijkstra search in Python -

i've played around writing own heap , trying out directed dijkstra's algorithm using heap store distances.

i've cross-checked answers bellman-ford (and on paper) i'm confident runs correctly, seems slow liking. i've made own graph class hold value of vertices/the length/head/tail of edges

def dijkstra(g,root):     ###initialize values     root.value=0     h=heap.heap(root)     v in g.vertices:         if v==root:             continue         v.value=float('inf')         h.insert(v)     while len(h.nodes)>1:         m=h.extractmin()         ##only works directed graphs          e in m.edges:             if (e.v in h.nodes) , e.v.value>m.value+e.d:             #if head of min vrtx in heap                 e.v.value=m.value+e.d                 h.check_parent(h.nodes.index(e.v)) #percolate  

on input of 50k edges , 1k nodes, takes >30sec complete. reasonable time expect python? assuming algorithm correct, heap limiting factor?

(also know i'm directly modifying/accessing members of class, ie v.value=... , bad practice? haven't declared them private)

thanks input!

is reasonable time expect python?

unable answer without knowing system specifications. try comparing against pre-built data structure e.g. https://docs.python.org/2/library/heapq.html

would heap limiting factor?

yes.

is bad practice?

this question bit out of place. asking oo @ same time asking algorithms.

finally, ensure heap implementation can achieve following in o(1) instead of o(n):

if (e.v in h.nodes) 

you don't have support operation in heap, btw. can have boolean property vertices , set v.inheap = true when it's added heap, , set false when extracted heap.