मुझे डिजस्ट्रा के एल्गोरिदम का जावा कार्यान्वयन कहां मिल सकता है?

Question

मैं डिजस्ट्रा के एल्गोरिदम के सामान्य जावा कार्यान्वयन की तलाश में हूं। मैंने इसे अपने आप पर कोड करने का प्रयास किया है, लेकिन मैं समस्याओं में भाग रहा हूं। अगर यह मदद करता है, तो मुझे पता है कि ग्राफ हमेशा जुड़े हुए हैं। क्या किसी को इस तरह के कार्यान्वयन के बारे में पता है?

धन्यवाद!

Answer 1

यह पूरी तरह से निर्बाध है, लेकिन मैंने थोड़ी देर पहले फिबोनैकी ढेर का उपयोग करके डिजस्ट्रा के एल्गोरिदम के कार्यान्वयन को कोड किया और इसे अपनी व्यक्तिगत वेबसाइट पर पोस्ट किया। आप यहाँ कोड पा सकते हैं:

• Dijkstra's algorithm
• Fibonacci heap

मैं कैसे एल्गोरिथ्म काम करता है इंगित करने के लिए कोड टिप्पणी करने की कोशिश की है, क्या मान्यताओं यह, बना रहा है आदि, इसलिए उम्मीद है यह पढ़ने और समझने में आसान है। अगर मुझे इसके बारे में कुछ पता है तो मुझे बताएं कि मैं आपके लिए स्पष्टीकरण दे सकता हूं।

आशा है कि इससे मदद मिलती है!

Answer 2

आप इस मतलब है:

(जावा कार्यान्वयन का उल्लेख लिंक पर पाया जा सकता है (इस जवाब के नीचे)

// 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/

Answer 3

JGrapht से मिला एक है ग्राफ के लिए सामान्य जावा लाइब्रेरी। डिजस्ट्रा का एल्गोरिदम भी कार्यान्वित किया गया है।

Answer 4

विश्वविद्यालयों से अच्छे संसाधन

• न्यूयॉर्क विश्वविद्यालय से http://www.cs.nyu.edu/~vs667/development/~DijkstraAlgorithm/

• Princton विश्वविद्यालय से कम से http://algs4.cs.princeton.edu/41undirected/Graph.java.html

---

पर भी vogella http://www.vogella.com/articles/JavaAlgorithmsDijkstra/article.html