मैं सूची ट्रैवर्सल कैसे करूं?

Question

मैंने हाल ही में एक परियोजना शुरू की है जिसमें लंदन Ungerground डेटासेट से डेटा का उपयोग करना शामिल है, ताकि किसी दिए गए स्टेशन से मिनटों की दूरी तय हो सके।

अब तक मैं डेटासेट से डेटा में पार्स करने और प्रत्येक स्टेशन के बीच संभावित मार्ग बनाने में सक्षम हूं। मैं अब मार्ग वस्तुओं जो निम्नलिखित गुण होते हैं की एक सूची है:

Parent - the first station 
Child - the next linked station 
Line - whichever line the station is on 
Time - the time between the two stations 

डेटा मैं वर्तमान में है, विक्टोरिया एक प्रारंभिक स्टेशन के रूप में उपयोग कर रहा है:

मैं अपने उत्पादन स्वरूपित किया है यह करने के लिए आसान बनाने के लिए पढ़ें, लेकिन प्रत्येक पंक्ति एक मार्ग वस्तु का प्रतिनिधित्व है। तो आपके पास प्रारंभिक स्टेशन, समय, अगला स्टेशन और रेखा है।

VICTORIA => 1 <= PIMLICO : Victoria 
VICTORIA => 2 <= GREEN PARK : Victoria 
VICTORIA => 2 <= ST JAMES PARK : Circle 
VICTORIA => 2 <= SLOANE SQUARE : Circle 
PIMLICO => 2 <= VAUXHALL : Victoria 
GREEN PARK => 2 <= OXFORD CIRCUS : Victoria 
GREEN PARK => 1 <= WESTMINSTER : Jubilee 
GREEN PARK => 2 <= BOND STREET : Jubilee 
GREEN PARK => 1 <= PICCADILLY CIRCUS : Piccadilly 
GREEN PARK => 1 <= HYDE PARK CORNER : Piccadilly 
ST JAMES PARK => 1 <= WESTMINSTER : Circle 
SLOANE SQUARE => 1 <= SOUTH KENSINGTON : Circle 
VAUXHALL => 2 <= STOCKWELL : Victoria 
VAUXHALL => 2 <= PIMLICO : Victoria 
OXFORD CIRCUS => 1 <= PICCADILLY CIRCUS : Bakerloo 
OXFORD CIRCUS => 2 <= REGENTS PARK : Bakerloo 
OXFORD CIRCUS => 2 <= TOTTENHAM COURT ROAD : Central 
OXFORD CIRCUS => 1 <= BOND STREET : Central 
OXFORD CIRCUS => 2 <= GREEN PARK : Victoria 
OXFORD CIRCUS => 1 <= WARREN STREET : Victoria 

विकटोरिया से सभी संभावित मार्गों को इकट्ठा करने का सबसे अच्छा तरीका क्या होगा?

उदाहरण के लिए:

VICTORIA > GREEN PARK > WESTMINSTER 
VICTORIA > GREEN PARK > BOND STREET 
VICTORIA > PIMLICO > VAUXHALL 

Answer 1

एक ग्राफ़ थ्योरी समस्या की तरह लगता है। मेरा मनपसंद!

"सभी संभावित मार्ग" ढूंढने में समस्या यह है कि, आपके द्वारा दिए गए डेटा (या इस स्थिति में कोई यथार्थवादी डेटासेट) के साथ, आपको लूप का सामना करना पड़ रहा है। इसलिए, किसी भी दिए गए मार्ग के लिए, आपको यह सुनिश्चित करने की आवश्यकता होगी कि प्रत्येक स्टेशन केवल पर जायेगा।

चूंकि आपके पास एक ही प्रारंभिक बिंदु है, इसलिए मैं Djikstra's Alogrithm की अनुशंसा करता हूं। यह VICTORIA से प्रत्येक अन्य स्टेशन पर एक पथ (वास्तव में, सबसे छोटा रास्ता) मिलेगा। कम से कम, हर दूसरे स्टेशन जो पहुंच योग्य है। यह एल्गोरिदम लागू करने के लिए एक प्रसिद्ध, तेज़ और अपेक्षाकृत आसान है। सामान्य रूप से ओ (एन^2) समय में चलता है, लेकिन कुछ डेटा संरचना jimmying के साथ ओ (एम + nlogn) में मालिश किया जा सकता है।

उम्मीद है कि कम से कम आपको सही रास्ते पर मिल जाए!