स्रोत से सभी शोर पथों को एक डिग्राफ में - सभी एल्गोरिदम, ग्राफ़-एल्गोरिदम, सबसे छोटा-पथ, निर्देशित-ग्राफ़ में ढूंढना

हमें पॉजिटिव एज वेट और न्यूनतम दूरी के साथ एक निर्देशित ग्राफ जी (संभवतः चक्र के साथ) दिया जाता है D[v] हर शिखर पर v एक स्रोत से भी दिया जाता है (डी इस तरह एक सरणी है)। समस्या सरणी खोजने के लिए है N[v] = number लंबाई के पथ D[v] s से v तक, रैखिक समय में।

अब यह एक होमवर्क की समस्या है जिसे मैंने किया हैकाफी लंबे समय से संघर्ष कर रहे हैं। मैं निम्नलिखित विचार के साथ काम कर रहा था: मैं "जी के एक एसाइक्जिक सबग्राफ को चुनकर साइकिल को हटाने की कोशिश कर रहा हूं, और फिर सबग्राफ में एस से वी तक के सबसे छोटे रास्तों को खोजने की कोशिश करता हूं।

लेकिन मैं स्पष्ट रूप से यह पता नहीं लगा सकता कि क्या करना है, इसलिए मैं किसी भी मदद की सराहना करता हूं, जैसे कि क्या करना है।

उत्तर:

आप उपयोग कर सकते हैं गतिशील प्रोग्रामिंग यहां पहुंचें, और जाने के दौरान रास्ते की संख्या भरें, यदि D[u] + w(u,v) = D[v], कुछ इस तरह:

N = [0,...,0]
N[s] = 1 //empty path
For each vertex v, in *ascending* order of `D[v]`:
for each edge (u,v) such that D[u] < D[v]:
if D[u] + w(u,v) = D[v]: //just found new shortest paths, using (u,v)!
N[v] += N[u]

जटिलता है O(VlogV + E)यह मानते हुए कि ग्राफ़ को स्पार्स नहीं किया गया है, O(E) हावी है।

स्पष्टीकरण:

अगर सबसे छोटा रास्ता है v0->v1->...->v_(k-1)->v_k से v0 सेवा मेरे v_k, फिर v0->...->v_(k-1) से सबसे छोटा रास्ता है v0 सेवा मेरे v_k-1, इस प्रकार - जब पुनरावृति v_k - N[v_(k-1)] पहले से ही पूरी तरह से गणना की गई थी (याद रखें, सभी किनारों में सकारात्मक भार हैं, और D[V_k-1] < D[v_k], और हम के बढ़ते मूल्य से पुनरावृत्ति कर रहे हैं D[v])।
इसके बाद, पथ v0->...->v_(k-1) संख्या में गिना जाता है N[V_(k-1)] इस समय।
जबसे v0->...->v_(k-1)-v_k सबसे छोटा रास्ता है - इसका मतलब है D[v_(k-1)] + w(v_k-1,v_k) = D[v_k] - इस प्रकार स्थिति पकड़ में आ जाएगी, और हम इस पथ की गिनती जोड़ देंगे N[v_k].

ध्यान दें कि इस एल्गोरिथ्म के लिए प्रमाण मूल रूप से प्रेरण होगा जो इस स्पष्टीकरण के दिशानिर्देशों का अधिक औपचारिक रूप से पालन करेगा।