समाधान बल को बल देना है। आप इसे गति देने के लिए कुछ अनुकूलन कर सकते हैं, कुछ छोटे हैं, कुछ बहुत जटिल हैं। मुझे संदेह है कि आप इसे डेस्कटॉप कंप्यूटर पर 18 000 नोड्स के लिए पर्याप्त तेज़ी से काम करने के लिए प्राप्त कर सकते हैं, और यहां तक कि यदि आप मुझे नहीं जानते कि कैसे। यहां बताया गया है कि ब्रूटफोर्स कैसे काम करता है।
नोट: डिजस्ट्रा और अन्य सबसे कम पथ एल्गोरिदम इस समस्या के लिए काम नहीं करेंगे यदि आप एक सटीक उत्तर में रूचि रखते हैं। 1 - 2 (4), 1 - 3 (100), 2 - 3 (5), 3 - 5 (200), 3 - 4 (7), 4 - 5 (1000)
Let the root be 1. We call getLongestPath(1, 0);
2 is marked as visited and getLongestPath(2, 4); is called
D[2] = 0 < currSum = 4 so D[2] = 4.
3 is marked as visited and getLongestPath(3, 4 + 5); is called
D[3] = 0 < currSum = 9 so D[3] = 9.
4 is marked as visited and getLongestPath(4, 9 + 7); is called
D[4] = 0 < currSum = 16 so D[4] = 16.
5 is marked as visited and getLongestPath(5, 16 + 1000); is called
D[5] = 0 < currSum = 1016 so D[5] = 1016.
getLongestPath(3, 1016 + 200); is called, but node 3 is marked as visited, so nothing happens.
Node 5 has no more child nodes, so the function marks 5 as not visited and backtracks to 4. The backtracking will happen until node 1 is hit, which will end up setting D[3] = 100 and updating more nodes.
यहाँ यह iteratively यह कैसी दिखाई देगी (परीक्षण नहीं है, बस एक मूल विचार):
Start at a root node *root*
Let D[i] = longest path from node *root* to node i. D[*root*] = 0, and the others are also 0.
void getLongestPath(node, currSum)
{
if node is visited
return;
mark node as visited;
if D[node] < currSum
D[node] = currSum;
for each child i of node do
getLongestPath(i, currSum + EdgeWeight(i, node));
mark node as not visited;
}
के इस ग्राफ पर हाथ से चलाते हैं
Let st be a stack, the rest remains unchanged;
void getLongestPath(root)
{
st.push(pair(root, 0));
while st is not empty
{
topStack = st.top();
if topStack.node is visited
goto end;
mark topStack.node as visited;
if D[topStack.node] < topStack.sum
D[topStack.node = topStack.sum;
if topStack.node has a remaining child (*)
st.push(pair(nextchild of topStack.node, topStack.sum + edge cost of topStack.node - nextchild))
end:
mark topStack.node as not visited
st.pop();
}
}
(*) - यह एक समस्या है - आपको प्रत्येक नोड के लिए अगले बच्चे को पॉइंटर रखना होगा, क्योंकि यह थोड़ी देर के लूप के विभिन्न पुनरावृत्तियों के बीच बदल सकता है और यहां तक कि खुद को रीसेट कर सकता है (जब आप पॉप करते हैं तो सूचक खुद को रीसेट करता है ई topStack.node ढेर से नोड, इसलिए इसे रीसेट करना सुनिश्चित करें)। लिंक किए गए सूचियों पर इसे लागू करना सबसे आसान है, हालांकि आपको int[] सूचियों या vector<int> सूचियों का उपयोग करना चाहिए, ताकि पॉइंटर्स को स्टोर करने में सक्षम हो और यादृच्छिक पहुंच हो, क्योंकि आपको इसकी आवश्यकता होगी। आप उदाहरण के लिए next[i] = next child of node i in its adjacency list रख सकते हैं और तदनुसार अपडेट कर सकते हैं। आपके पास कुछ किनारे के मामले हो सकते हैं और उन्हें end: स्थितियों की आवश्यकता हो सकती है: एक सामान्य और एक ऐसा होता है जब आप पहले से देखे गए नोड पर जाते हैं, तो किस स्थिति में पॉइंटर्स को रीसेट करने की आवश्यकता नहीं होती है। इससे बचने के लिए स्टैक पर कुछ धक्का देने का फैसला करने से पहले शायद विज़िट की गई स्थिति को स्थानांतरित करें।
देखें मैंने क्यों कहा कि आपको परेशान नहीं होना चाहिए? :)
चक्रीय ग्राफ पर सबसे लंबा रास्ता अनंत लंबाई का होगा, है ना? आप बस गोल और गोल और गोल और दौर जा रहे हैं ... – qrdl
भले ही मैं देखे गए नोड्स को चिह्नित करता हूं, इसलिए मैं उनसे फिर से नहीं जाता? ऐसा कुछ है जो मैं अभी भी समझ नहीं पा रहा हूं क्यों। मेरे दिमाग में, यह डिज्कास्ट्रा एल्गोरिदम की तरह होना चाहिए, केवल "रिवर्स"। नीचे सुझाए गए की तरह, लेकिन मैं इसे काम करने में सक्षम नहीं हूं। एल्गोरिदम खत्म होता है, लेकिन परिणाम सही नहीं लगते हैं। –