我在哪裏可以得到Dijkstra算法的Java實現？

我正在尋找Dijkstra算法的通用Java實現。我試着自己編碼，但我一直遇到問題。如果有幫助，我知道圖表始終處於連接狀態。有誰知道這樣的實現？我在哪裏可以得到Dijkstra算法的Java實現？

謝謝！

來源

2011-08-25 MozenRath

這是完全無恥的，但我編寫了使用斐波那契堆的Dijkstra算法的實現，並將其發佈到我的個人網站。您可以在這裏找到代碼：

我試着註釋代碼，用於指示如何算法的工作，它使什麼假設，等等，所以希望它是易於閱讀和理解。讓我知道如果有什麼關於它我可以爲你澄清。

希望這會有所幫助！

來源

2011-08-25 21:28:47 templatetypedef

我需要方向感簡單連接圖s :) – MozenRath

@ Piyush-您可以使用有向圖來表示無向圖 - 只需讓每對連接的節點互相指向即可。 – templatetypedef

@templatetypedef在我看來，你的代碼是我在網上看到的最乾淨的代碼，你是否也可以共享鏈接作爲參數傳遞給DirectedGraph？ – JavaDeveloper

你的意思是這樣的：

（Java實現可提到的鏈接中找到（見這個答案的底部）

// initialize d to infinity, π and Q to empty 
d = (∞) 
π =() 
S = Q =() 

add s to Q 
d(s) = 0 

while Q is not empty 
{ 
    u = extract-minimum(Q) 
    add u to S 
    relax-neighbors(u) 
} 

relax-neighbors(u) 
{ 
    for each vertex v adjacent to u, v not in S 
    { 
      if d(v) > d(u) + [u,v] // a shorter distance exists 
      { 
       d(v) = d(u) + [u,v] 
       π(v) = u 
       add v to Q 
      } 
    } 
} 

extract-minimum(Q) 
{ 
    find the smallest (as defined by d) vertex in Q 
    remove it from Q and return it 
}

編輯：得到這個從http://renaud.waldura.com/doc/java/dijkstra/

來源

2011-08-25 21:29:33

這不是在我的Java版本中編譯。 *你使用什麼版本？ – Patrick87

我認爲OP是專門尋找Java代碼而不是僞代碼;這個問題表明OP已經找到了僞代碼，但是難以將其翻譯成Java。 – templatetypedef

可以在鏈接中找到Java實現:) –

JGrapht是通用的Java圖形庫，實現dijkstra算法。

來源

2011-08-25 21:30:57 Heisenbug

大學的好資源