Dijkstra Shortest Path Algorithm In Hindi

हेलो फ्रेंड्स, आज के इस ब्लॉग पोस्ट(Dijkstra Shortest Path Algorithm In Hindi) में मैं आपको Dijkstra shortest path algorithm के बारे में हिंदी में बताने जा रहा हूँ | इस Dijkstra shortest path algorithm के तहत हम किसी ग्राफ के अंदर स्टार्टिंग नोड से एंडिंग नोड तक के लिए शॉर्टेस्ट अथवा optimal path find करते है |

इस ब्लॉग पोस्ट में हम Dijkstra shortest path algorithm से रिलेटेड कुछ और मत्वपूर्ण questions को discuss करेंगे जैसे कि:

What is Dijkstra’s(Dijkstra Shortest Path Algorithm In Hindi) algorithm for example? How do you use Dijkstra’s algorithm? Does Dijkstra’s algorithm always work? Is Dijkstra a BF? Why the Dijkstra algorithm is greedy? Which shortest path algorithm is best?….

…How does the Kruskal algorithm work? Is Dijkstra greedy or dynamic programming? How do you find the shortest path algorithm? How do you solve Dijkstra’s problem? How does Prim’s algorithm work?…|Dijkstra Shortest Path Algorithm In Hindi|

…What is the time complexity of the Dijkstra algorithm? Why does Dijkstra fail negative weights? Does Google Maps use Dijkstra? What is the finiteness of the algorithm? What do you mean by shortest path algorithm?…|Dijkstra Shortest Path Algorithm In Hindi|

…What is single source shortest path algorithm? Is Bellman Ford greedy? What algorithm does GPS use?|Dijkstra Shortest Path Algorithm In Hindi|

आप में से बहुत से लोगो ने data structure के अंदर dijkstra shortest path algorithm को स्टडी किया होगा | अगर आप अभी भी इस Dijkstra algorithm को लेकर कंफ्यूज है तो आप बिलकुल भी चिंता न करें | इस ब्लॉग पोस्ट में हम आपको विस्तार से इस Dijkstra shortest path algorithm के बारे हिंदी में बताएँगे|Dijkstra Shortest Path Algorithm In Hindi|

दो nodes के बीच हम shortest डिस्टेंस कैसे फंड करते है ?| Dijkstra shortest path algorithm procedure क्या है ?

Dijkstra algorithm की तकनीक बहुत सारे forms अथवा scenario में उपयोग की जाती है क्योकि यह समझने में बहुत ही सरल और उपयोग करने में बहुत ही आसान होती है |

यहाँ पर हम आपको जिस सन्दर्भ में Dijkstra shortest path algorithm समझाने वाले है वह एक subnet का ग्राफ है | यहाँ पर प्रत्येक नोड एक राऊटर है और जो उन्हें जोड़ने वाली arc है वो communication link है |

किसी भी दो routers अथवा node के बीच में हमें shortest path find करना है और इसी प्रोसेस को रिपीट करते करते हमें सोर्स से डेस्टिनेशन तक पहुंचना है | और लेंथ को measure करने का एक तरीका hops के नंबर को काउंट करना है | hops जो होता है वो एक नोड से दूसरे नोड तक पहुंचने का डिस्टेंस होता है, जो किसी भी distance unit में हो सकता है |

नीचे एक ग्राफ दिया गया है और इस ग्राफ में हमें A से D तक का shortest path find करना है | वैसे तो इसके लिए कई सारे matrix तैयार की जा सकती है और फिर हमें sabse optimal वाले को select करके फिर उस node से आगे की तरफ बढ़ना है |

Dijkstra shortest path algorithmnew
Fig 1. Dijkstra’s Algorithm: Dijkstra shortest path algorithm

स्टार्टिंग में सभी नोड्स की लेबलिंग infinity से होगी और जैसे जैसे हम A से आगे की नोड की तरफ बढ़ते जायेंगे वैसे वैसे हम अपनी labling और hops चेंज करते जायेंगे | कुछ labling temporary हो सकती है और कुछ permanet |

जो भी node shortest path के लिए फाइनल हो जायेगा वो लेबलिंग permanet हो जाएगी और फिर उसे कोई चेंज नहीं कर पायेगा | और इसी तरह हम A से D तक तक shortest path find कर लेंगे और इसी path को select करके राऊटर A से data packet को ट्रांसमिट कर देंगे|

जैसे कि नीचे दिए गए ग्राफ में कई सारे path traverse करने के बाद जो फाइनल optimal path हमें मिलेगा वो होगा ‘ABEFHD ‘. तो दोस्तों इस Dijkstra shortest path algorithm में कठिन कुछ भी नहीं है बस हमें सबसे सुगम या ऑप्टीमल रास्ता ढूंढ़ना होता है अपने diestination तक पहुंचने के लिए |

यहाँ पर हम starting node से चलना चालू करते है और फिर उसके adjacent सभी नोड्स को इंस्पेक्ट कर के देख लेते है और उनमे हो सबसे शॉर्टेस्ट होता है हम उसे सेलेक्ट कर लेते है | और फिर इस distance को परमानेंट लेबलिंग देते है |

फिर हम दूसरे नोड जो परमानेंट decide हो चुका है उसके adjacent सभी नोड को इंस्पेक्ट करते है और उन पर लेबलिंग करते है और जहाँ पर जरुरत हो वहां पर रेलबलिंग भी करते है | और फिर सबसे shortest path को परमानेंट करते है |

फिर यही प्रोसेस करते करते हम हमने destination node तक पहुंचने का सबसे shortest path ढूँढ निकालते है|

Dijkstra Shortest Path Graph Explanation:

जैसे कि ऊपर दिए हुए ग्राफ में सबसे पहले हम नोड A से start करते है और फिर A के adjacent जितने नोड है जैसे यहाँ पर A के adjacent G और B नोड है तो उन दोनों का डिस्टेंस find करते है और उनमे जो भी shortest है उसे permanet मार्क कर देते है और G को tentative मार्क करके लेबलिंग कर देते है |

इसके बाद हम B जो की हमने पहले permanet किया था से आगे चलना शुरू करते है | और अब B के adjacent नोड को देखते है | और यहाँ पर बी के adjacent नोड होते है C एंड E | क्य और E में जो shortest path होता है वो होता है E का तो इस बार हम इसे permanet मार्क कर देते है |

और अब हमारा अगला starting नोड होता है E और यहाँ पर E के जो adjacent नोड होते है वो है F एंड G | यहाँ पर हम G नोड जो अभी तक tentative था उसको हम रेलबलिंग करते है और उसे अब उसे परमानेंट नोड बनाते है | और F को भी लेबल करते है |

इसके बाद हम G को स्टार्टिंग नोड मान कर उसके adjacent नोड को इंस्पेक्ट करते है और उसका adjacent नोड होता है H | और यहाँ पर हम हम H की लेबलिंग करते है और उसे tentative मार्क करते है |

अब हम H को स्टार्टिंग नोड मान कर फिर से adjacent नोड F एंड D को इंस्पेक्ट करते है और इस बार हम H को रेलबल भी करते है | और अब उसे परमानेंट मार्क कर देते है | और D की भी लेबलिंग कर देते है |

अब यहाँ पर हमारा पूरा node inspection खत्म हो जाता है और हमें हमारा फाइनल route मिल जाता है | और यह रूट होता है ABEFHG |

Quick Q&A:

Dijkstra shortest path algorithm को आप कैसे use करते है ?

Dijkstra shortest path algorithm को use करने का एक प्रोसीजर जो नीचे दिया गया है:

सबसे पहले तो आप ग्राफ में सभी नोड्स के बीच के डिस्टेंस को इनिशियलाइज़ कर ले|
इसके बाद आप किसी भी एक नोड को स्टार्टिंग नोड मान कर उसके Adjacent नोड को इंस्पेक्ट करें |
Adjacent नोड्स में जिसका distance सबसे कम हो उसे सेलेक्ट करें और उस पर लेबलिंग करें |
और फिर से shortest node को starting node मान कर उसके Adjacent nodes को इंस्पेक्ट करें और shortest distance node find करें |
और इसी प्रोसेस को तब तक रिपीट करें जब तक आप सभी नोड्स inspect न कर ले |
और फाइनली आप को shortest route मिल जायेगा |

क्या Dijkstra algorithm हमेशा काम करती है ?

Dijkstra algorithm सभी non -negative weighted और directed ग्राफ के लिए बहुत अच्छे से काम करती है |

क्या Dijkstra BFS है?

हाँ हम ऐसा कह सकते है | Dijkstra algorithm वैसे ही काम करती है जैसे कि BFS | Dijkstra algorithm का उपयोग हम two vertex के बीच shortest distance पता करने के लिए use करते है | तो हम ऐसा conclude कर सकते है कि Dijkstra algorithm को हम BFS की तरह implement कर सकते है priority queue के साथ |

Dijkstra algorithm greedy क्यों है ?

Dijkstra को हम greedy भी consider कर सकते है क्योकि इसके अंदर हम shortes अथवा closest vertex का पता करते है | पर यहाँ पर हम vertex की value को पिछले कैलकुलेशन के बेस पर अपडेट भी कर देते है तो इसलिए हम इसे dynamic algorithm consider भी कर सकते है | पर ओवरआल हम इसे greedy consider करने की वजह dynamic कंसीडर करना पसंद करेंगे क्योकि हम A से B तक का shortest डिस्टेंस find करने के लिए कोई step by step प्रोसेस predict नहीं कर सकते है |

कौन सी shortest path algorithm सबसे अच्छी है ?

Dijkstra shortest path algorithm की मदद से हम एक नोड से shortest path का पता कर सकते है | पर Floyd-Warshall अल्गोरिथम की मदद से हम प्रत्येक दो vertex के बीच shortest distance का पता कर सकते है | Floyd -Warshall algorithm का running time Dijkstra algorithm से ज्यादा है |

BFS और Dijkstra algorithm में क्या difference है ?

दोनों ही तकनीक बहुत ही similar है | दोनों का उपयोग ही shortest distance को find करने के लिए किया जाता है | पर BFS में हम undirected graph में nodes के बीच shortest distance find करते है जबकि Dijkstra shortest path अल्गोरिथ्म में हम directed graph में यही प्रोसेस करते है |

Bellman -Ford और Dijkstra algorithm में क्या डिफरेंस है ?

दोनों ही algorithm का उपयोग हम vertex के बीच shortest distance find करने के लिए करते है | पर Bellman -Ford algorithm negative weight को भी हैंडल कर सकती है, जबकि Dijkstra algorithm negative weights को handle नहीं कर पाती है|

क्या Dijkstra algorithm का use करके हम longest path भी find कर सकते है ?

वैसे तो Dijkstra algorithm को shortest path find करने के लिए design किया गया है | पर अगर हम इसमें कुछ सिंपल मॉडिफिकेशन अपडेट कर दे तो हम इसकी मदद से लांगेस्ट path भी find कर सकते है |

क्या गूगल मैप भी Dijkstra algorithm का use करती है ?

यह एक फैक्ट है कि Dijkstra algorithm सभी shortest path finding application को strength प्रोवाइड करती है | और गूगल मैप भी shortest distance और route find करने के लिए Dijkstra shortest path algorithm का use करती है | Google जैसे और भी कई navigation application जैसे कि apple map भी इस Dijkstra algorithm का use कर रही है |

application इस algorithm को अपने हिसाब से modify और update कर सकती है पर इस algorithm का बेसिक तो सभी navigation application के लिए फायदेमंद है |

Dijkstra algorithm negative weight को handle क्यों नहीं कर पाती है ?

दरअसल में Dijkstra algorithm का main कम है optimal path find करना न कि कोई भी path find करना | इसलिए negative weight के साथ यह प्रोसेस एक लूप में फास सकती है क्योकि इसमें previous नोड कैलकुलेशन को भी use करना पड़ता है | और इस तरह यह नेगेटिव वेट के साथ एक गलत route output में दे सकती है |Dijkstra Shortest Path Algorithm In Hindi|

Conclusion:

तो दोस्तों इस ब्लॉग पोस्ट(Dijkstra Shortest Path Algorithm In Hindi) में हमने Dijkstra shortest path algorithm के बारे में discuss किया और इस algorithm को एक example के जरिये step by step समझा | Dijkstra shortest path algorithm एक बहुत ही आसान और simple algorithm है | यहाँ पर हम एक node या vertex से डेस्टिनेशन node तक का shortest अथवा optimal route फंड करते है |

तो दोस्तों इस ब्लॉग पोस्ट में हमने Dijkstra shortest path algorithm से related कुछ महत्वपूर्ण questions को डिसकस किया है जैसे कि What is Dijkstra’s algorithm with an example, How do you use Dijkstra’s algorithm, Does Dijkstra’s algorithm always work, Is Dijkstra a BF, Why Dijkstra algorithm is greedy, Which shortest path algorithm is best, How does Kruskal algorithm work, Is Dijkstra greedy or dynamic programming, How do you find shortest path algorithm, How do you solve Dijkstra’s problem

इस ब्लॉग(Dijkstra Shortest Path Algorithm In Hindi) को लेकर आपके मन में कोई भी प्रश्न है तो आप हमें इस पते [email protected]पर ईमेल लिख सकते है|

आशा करता हूँ, कि आपने इस पोस्ट Dijkstra Shortest Path Algorithm In Hindi को खूब एन्जॉय किया होगा|

आप स्वतंत्रता पूर्वक अपना बहुमूल्य फीडबैक और कमेंट यहाँ पर दे सकते है|

आपका समय शुभ हो|

Anurag

I am a blogger by passion, a software engineer by profession, a singer by consideration and rest of things that I do is for my destination.