Hello दोस्तों! आज मैं आपको इस पोस्ट में Shortest Path Problem for graph in data structure के बारें में बताऊंगा, और इसके example को भी पढेंगे,
तो चलिए शुरू करते हैं:-
Shortest Path Problem for Graph in Data Structure
हमने graph को traverse करते समय देखा की हम graph को graph की edges के द्वारा travel करते ही किसी –किसी case मे ऐसे भी हो सकता है.
की इन edges पर कुछ weight दिया गया है यह weight की दूरियों के उपर असर डाल सकता है ।
निम्न चित्र मे दर्शाये गए graph का अध्ययन करे । हम graph की प्रत्येक node से graph की दूसरी प्रत्येक node पर जा सकते है ।
माना हमे A node से C node पर जाना है तो हमारे पास दो रास्ते है –
A->B->C तथा A->E->D->C
देखने मे तो दूसरा रास्ता लंबा है परंतु यदि हम edge पर लिखे weight से गणना करें तो दूसरे रास्ते को चुनेगे ।
इस प्रकार हम सदैव एक छोटे –छोटे path को ही चुनेंगे ।
यहाँ पर हमें graph को दोहरा लेना चाहिए । graph मे path , vertices का एक क्रम है
जिस प्रकारवे edge मे है path की लंबाई उसकी edge पर लिखे weight के जोड़ के बराबर होती है ।
destination vertex
path की पहली vertex , path की source vertex तथा अंतिम vertex, path की destination vertex कहलाती है ।
अब हम उपरोक्त चित्र मे graph के लिए shortest path निकलेंगे।
यहां पर हम देख देख सकते है A से D तक जाने के अनेक रास्ते है ।
पहले path की लंबाई A->B->C->D 2+2+2=6
दूसरे path की लंबाई A->G->I->D 3+1+1=5
तीसरे path की लंबाई A->B->E->D 2+1+1=4
हम देख सकते है की A->B->E->D path की कीमत (cost) सबसे कम है , इसलिए हम इसी रास्ते को अपनाएँगे ।
किसी भी graph मे shortest path को खोजने के लिए प्रयोग किए जाने वाला तरीका Dijkastara का method कहलाता है । इस तरीके को प्रयोग करने के लिए निम्नलिखित algorithm को ध्यान मे रखते है ।
status 1 = ready state
status 2 = colored state
1 step – graph की सभी node को ready state मे initialize करा दे । (status 1)
2 step – starting vertex का status बदल दे । (status 2)
3 step – loop 4 को तब तक दोहराएँ जब तक की सभी node colored status मे नहीं परिवर्तित कर दे ।
4 step – n की adjacent node जिसका सबसे कम weight हो ,उसका status बदलकर colored status कर दें ।
5 step – step2 का loop खत्म हुआ ।
6 step – Exit
Example:-
इसे अब उदाहरण की सहायता से समझेंगे ।
हम यहां देख सकते है की सबसे कम weight वाली unvisited edge AB है
इसलिए हम इसकी unvisited incident vertices को पुरानी शर्तो के अनुसार ही table मे जोड़ देंगे ।
हम यहां देख सकते है की सबसे कम weight वाली unvisited edges AE,AG और AH है ।
इन तीनों मे से किसी भी edge को पहले चुना जा सकता है । यहां हम AE ले रहे है
और इसकी unvisited incident vertices को पुरानी शर्तो के अनुसार table मे जोड़ लेंगे ।
अब हा, AG की सारी unvisited incident vertices को पुरानी शर्तो के अनुसार लिस्ट मे जोड़ देंगे ।
अतः हम देख सकते है यदि A को I पर पहुँचाना है तो उसकी कीमत (cost) केवल 4 है ।
A से अन्य node पर पहुँचने के लिए path निम्नलिखित है
यहाँ पर प्रत्येक node उस पर A node से पहुँचने का रास्ता(path) व कीमत(cost) बता रही है|
निवेदन:-
अगर आपके लिए यह आर्टिकल useful रहा हो तो इसे अपने दोस्तों और classmates के साथ अवश्य share कीजिये, और या अन्य विषयों से related कोई question हो तो नीचे कमेंट के द्वारा बताइए. thanks.
इसे भी देखे:
Hello दोस्तों! नीचे दिए गए links पर click करके आपको हम इस पोस्ट में (Computer Online Test) की Practice कराएंगे जिससे आप अपने CCC, O level , कम्प्युटर GK की practice कर सकते है.
इस post के द्वारा आप अपनी कम्प्युटर की नॉलेज बड़ सकते है.
उसके साथ ही साथ आप अपने कई प्रकार के पेपरो की भी तैयरी भी कर सकते है.
जैसे की CCC, O level , कम्प्युटर GK की practice कर सकते है,