के बीच सबसे छोटा रास्ता प्राप्त करने के लिए डिजस्ट्रा के एल्गोरिदम को संशोधित करें, इसलिए मैंने इस तरह के समान प्रश्न देखे हैं, लेकिन बिल्कुल ठीक नहीं है जो मैं ढूंढ रहा हूं। मुझे एक कशेरुक एस (स्रोत) और एक कशेरुक एक्स (गंतव्य) के बीच सबसे छोटा रास्ता वापस करने के लिए डिजस्ट्रा के एल्गोरिदम को संशोधित करने की आवश्यकता है। मुझे लगता है कि मैंने यह पता लगाया है कि क्या करना है, लेकिन मुझे कुछ मदद चाहिए। यहां छद्म कोड मैंने संशोधित किया है।दो नोड्स
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
यह सही लगता है?
आपको इसकी आवश्यकता क्यों होगी इसे संशोधित करने के लिए? यह वही है जो यह करता है। जब आप सभी किनारों के वजन को 1 –
पर सेट करते हैं तो यह वह कोड है जिसे मैंने पहले ही संशोधित कर दिया है। तो अगर यह महान काम करता है। – csnate
इसके अलावा, जैसे ही डिजस्ट्रा में कशेरुक चयन लालची है, जैसे ही आपको "यू = गंतव्य" मिलता है, आप लूप को तोड़ सकते हैं। –