python - 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=... ，这是不好的做法吗？我没有明确声明它们是私有(private)的)

感谢您的输入!

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?

这个问题有点不对。您在询问算法的同时也在询问面向对象。

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

if (E.v in h.nodes)

顺便说一句，您不必支持堆中的操作。您可以简单地为顶点设置另一个 bool 属性，并在将其添加到堆时设置 v.inHeap = True，并在从堆中提取时将其设置为 False .