Pythonでの最適ダイレクトダイクストラの検索

Question

私は自分自身のヒープを作成し、距離を格納するためにヒープを使ってダイレクトダイクストラのアルゴリズムを試してみました。

私はBellman-Ford（と紙にも書かれている）との回答をクロスチェックしたので、正しく動作すると確信していますが、それは好みには遅すぎるようです。 50Kエッジと1Kのノードの入力のエッジ

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 

の私も頂点の値を保持するために自分自身のグラフクラスを作った/長さ/ヘッド/テールは、それは> 30秒完了するのにかかります。これはPythonで期待できる合理的な時間ですか？アルゴリズムが正しいと仮定すると、ヒープが制限要因になりますか？

（また、私は私が直接クラスのメンバーへのアクセス/修正するんだ、すなわちv.value = ...、その悪い習慣です？私は特に彼らがプライベートと宣言していないことを知っている）のための

感謝入力！

Answer 1

これはPythonで期待できる時間ですか？

システム仕様を知らなくてもこれに答えることができません。事前構築されたデータ構造と比較してみてください。 https://docs.python.org/2/library/heapq.html

私のヒープは制限要因ですか？

はい。

は悪い練習ですか？

この質問は、少しばかりです。あなたはアルゴリズムについて質問するのと同時にOOについて尋ねています。

最後に、あなたのヒープ実装がO(1)の代わりO(n)に以下を達成することができることを確認してください。

if (E.v in h.nodes) 

あなたはところで、あなたのヒープでの動作をサポートする必要はありません。頂点に別のブール値を設定し、ヒープに追加するときはv.inHeap = Trueと設定し、ヒープから抽出するときはFalseに設定することができます。