के-सबसे छोटा (वैकल्पिक) पथ एल्गोरिदम, जावा कार्यान्वयन

Question

क्या आप किसी भी जावा लाइब्रेरी की अनुशंसा कर सकते हैं जो कि कम-से-कम एल्गोरिदम लागू करता है -> वैकल्पिक तरीकों की खोज, निर्देशित मल्टीग्राफ में केवल सबसे छोटा नहीं है?

मुझे केवल जेजीआरटीटी मिली लेकिन वास्तव में बग (जिसे मैंने सबमिट किया) है लेकिन मुझे लगता है कि इसे ठीक करने में काफी समय लगेगा, क्या कोई अन्य उपलब्ध कार्यान्वयन है? जेजीआरटीटी को छोड़कर मुझे केवल एक छोटी सी परियोजनाएं मिलीं:/

या वैकल्पिक पथ दिखाने के लिए Disjktra सबसे छोटा पथ alg को संशोधित करना मुश्किल होगा?

धन्यवाद

Answer 1

2 संभावित विकल्प:

विकल्प 1. class KshortestPaththe MascOpt Package से एक के लिए एक अच्छा विकल्प है के-सबसे कम पथ के जावा कार्यान्वयन।

विकल्प 2. आप भी code.google.com से कोशिश कर सकते हैं यह एक एक व्यक्ति के प्रयास हो रहा है, लेकिन अच्छी बात यह है कि एल्गोरिथ्म साझा किया जाता है:। येन रैंकिंग - विवरण यहाँ हैं (http://www.ohloh.net/p/k-shortest-paths)

नोट: दिए गए ग्राफ में नोड्स के सभी जोड़े के बीच सबसे कम-पथ ढूंढना एक अलग समस्या है। Dijkstra vs. Floyd-Warshall पर यह SO प्रश्न देखें।

यह भी ध्यान दें कि समृद्ध ग्राफ के लिए k-shortest paths (डीजस्ट्रा) सबसे छोटा रास्ता - थोड़ी अधिक लागत वाले सबसे कम पथ पर शिखर के बीच वैकल्पिक पथ होते हैं।

मैं ओपी जावा कार्यान्वयन के लिए कहा है, लेकिन अगर लोगों को एक विकल्प है और अनुसंधान के लिए एक विकल्प है, तो क्रैन से kBestShortestPathspackage रूप में अच्छी तरह एक बहुत अच्छा विकल्प है।

उम्मीद है कि मदद करता है।

Answer 2

एक समान अनुरोध से पहले हुई है, लेकिन StackOverflow पर सभी रास्तों की तलाश में। Find all paths in a graph with DFS

आशा इस मदद करता है, उसका उत्तर दिया गया था, लेकिन सटीक समाधान के साथ नहीं है, लेकिन एक गाइड के अधिक

Answer 3

के-सबसे कम पथ ढूंढना वैकल्पिक पथ के समान सटीक समस्या नहीं है। अच्छा वैकल्पिक पथ अधिक जटिल हैं। Have a read जहां अन्य इसी तरह के दृष्टिकोण दिए गए हैं:

• k-सबसे छोटा पथ
• Pareto optimality
• पठार विधि
• जुर्माना दृष्टिकोण

पठार विधि थोड़ा सचित्र here है।

तो यह संभव है आप जर्मन तो this lecture is nice पढ़ने के लिए:

• उदासमय या दूरी के बारे में अनुकूलन => समस्या: दिलचस्प विकल्प
• dijunct रास्तों याद कर रहे हैं => एक ही समस्या
• k-कम से कम पथ => समस्या: वास्तविक विकल्प शायद पहले 1000 रास्तों के तहत नहीं है

पृष्ठ 5

तो अंतर्ज्ञान हमें बताता है: एक विकल्प में लगभग समान दूरी या समय होना चाहिए। लेकिन महत्वपूर्ण अलग होना चाहिए। तो पहला विचार: पथ ढूंढें जो लंबाई और समानता को कम करता है। समस्या: स्थानीय चक्कर हो सकते हैं। स्थानीय optimumality:

पेज 6

हम एक 3 कसौटी परिचय हर छोटी सब-पाथ एक कम से कम पथ की जरूरत है।