Python中最优定向Dijkstra搜索

Question

我尝试过编写自己的堆，并尝试使用堆存储距离的定向Dijkstra算法。在

我已经和贝尔曼·福特（Bellman Ford）交叉核对了答案（也在纸上），所以我确信它运行正常，但是它似乎太慢了，我不喜欢。我还创建了自己的Graph类来保存顶点值/边的长度/头/尾

def dijkstra(G,root):
    ###Initialize values
    root.value=0
    h=heap.Heap(root)
    for 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 for directed graphs 
        for E in m.edges:
            if (E.v in h.nodes) and E.v.value>m.value+E.d:
            #If head of the min vrtx is in the heap
                E.v.value=m.value+E.d
                h.check_parent(h.nodes.index(E.v)) #percolate up 

在50k个边和1k个节点的输入上，完成该操作需要超过30秒。现在是使用python的合理时机吗？假设算法是正确的，我的堆会是限制因素吗？在

（我也知道我直接修改/访问类的成员，比如v.value=。。。，这是坏习惯吗？我没有特别声明他们是私人的）

感谢您的输入！在

Answer 1

Is this a reasonable time to expect with python?

在不知道系统规格的情况下无法回答此问题。尝试与预构建的数据结构进行比较，例如https://docs.python.org/2/library/heapq.html

would my heap be the limiting factor?

是的。在

is that bad practice?

这个问题有点不合时宜。你在询问算法的同时也在问OO。在

最后，确保堆实现可以在O(1)而不是O(n)中实现以下目标：

if (E.v in h.nodes)

顺便说一句，您不必支持堆中的操作。您只需为顶点设置另一个布尔属性，并在将其添加到堆时设置v.inHeap = True，并在从堆中提取它时将其设置为False。在