2012-11-19 14 views
7

के बीच सबसे छोटा रास्ता प्राप्त करने के लिए डिजस्ट्रा के एल्गोरिदम को संशोधित करें, इसलिए मैंने इस तरह के समान प्रश्न देखे हैं, लेकिन बिल्कुल ठीक नहीं है जो मैं ढूंढ रहा हूं। मुझे एक कशेरुक एस (स्रोत) और एक कशेरुक एक्स (गंतव्य) के बीच सबसे छोटा रास्ता वापस करने के लिए डिजस्ट्रा के एल्गोरिदम को संशोधित करने की आवश्यकता है। मुझे लगता है कि मैंने यह पता लगाया है कि क्या करना है, लेकिन मुझे कुछ मदद चाहिए। यहां छद्म कोड मैंने संशोधित किया है।दो नोड्स

1 function Dijkstra(Graph, source, destination): 
2  for each vertex v in Graph:        // Initializations 
3   dist[v] := infinity ;         // Unknown distance function from 
4                 // source to v 
5   previous[v] := undefined ;        // Previous node in optimal path 
6  end for             // from source 
7  
8  dist[source] := 0 ;          // Distance from source to source 
9  Q := the set of all nodes in Graph ;      // All nodes in the graph are 
10                 // unoptimized - thus are in Q 
11  while Q is not empty:          // The main loop 
12   u := vertex in Q with smallest distance in dist[] ; // Start node in first case 
13   remove u from Q ; 
14   if dist[u] = infinity: 
15    break ;           // all remaining vertices are 
16   end if             // inaccessible from source 
17   
18   for each neighbor v of u:        // where v has not yet been 
19                 // removed from Q. 
20    alt := dist[u] + dist_between(u, v) ; 
21    if alt < dist[v]:         // Relax (u,v,a) 
22     dist[v] := alt ; 
23     previous[v] := u ; 
24     decrease-key v in Q;       // Reorder v in the Queue 
25    end if 
26   end for 
27  end while 
28 return dist[destination]; 

कोड विकिपीडिया से लिया गया है और संशोधित: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

यह सही लगता है?

+3

आपको इसकी आवश्यकता क्यों होगी इसे संशोधित करने के लिए? यह वही है जो यह करता है। जब आप सभी किनारों के वजन को 1 –

+0

पर सेट करते हैं तो यह वह कोड है जिसे मैंने पहले ही संशोधित कर दिया है। तो अगर यह महान काम करता है। – csnate

+1

इसके अलावा, जैसे ही डिजस्ट्रा में कशेरुक चयन लालची है, जैसे ही आपको "यू = गंतव्य" मिलता है, आप लूप को तोड़ सकते हैं। –

उत्तर

4

डिजस्ट्रा के एल्गोरिदम को संशोधित करने की आवश्यकता नहीं है, यह एक सभी जोड़े सबसे कम पथ एल्गोरिदम है। ऐसा लगता है कि आप दो विशिष्ट नोड्स के बीच सबसे छोटा रास्ता खोजने की कोशिश कर रहे हैं - डिजस्ट्रा इस जुर्माना को संभालता है।

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

+2

क्या? डिजस्ट्रा सभी जोड़े नहीं है। – rosstex

4

एकल स्रोत से शुरू होने वाले सबसे कम-पथ को खोजने के बाद, हमें पथ को मुद्रित करने के लिए अपने पूर्ववर्ती को बैकट्रैक करने के लिए DESTINATION से शुरुआत की आवश्यकता है। एल्गोरिथ्म का परिचय करने के लिए शिष्टाचार, एमआईटी प्रेस ऊपर

Print-Path(G,s,v) 
{ 
    if(v==s) 
     print s; 
    else if (pi[v]==NULL)  
     print "no path from "+s+" to "+v; 
    else{ 
     Print-Path(G,s,pi[v]) 
     print v; 
    } 
} 

कोड

2

इस दृष्टिकोण का सबसे अच्छा तरीका प्रत्येक पहुंच योग्य नोड वापस स्रोत, आमतौर पर वी से दर्शाया जाने से रास्तों के संदर्भ में सोचना है। आप के रूप में प्रत्येक दिए गए नोड की दूरी को अपडेट करें, वी के उस पथ पर अपने सीधा उत्तराधिकारी का ट्रैक रखें। वह नोड सबसे कम दूरी-से-वी पेड़ में दिया गया नोड का अभिभावक है। जब आप उस पैरेंट मैप को बनाते हैं, तो वी से डब्ल्यू से सबसे कम पथ खोजने के लिए रिवर्स ऑर्डर में पथ बनाते हैं: डब्ल्यू, पैरेंट [डब्ल्यू], पैरेंट [पैरेंट [डब्ल्यू]], ...

संबंधित मुद्दे