Dijkstra's एल्गोरिदम कंप्यूटर विज्ञान में एक लोकप्रिय तरीका है जिसका उपयोग एक ग्राफ में नोड्स के बीच सबसे छोटा पथ खोजने के लिए किया जाता है। यह व्यापक रूप से नेटवर्क रूटिंग, नक्शा नेविगेशन और विभिन्न अनुकूलन समस्याओं में लागू होता है। यह लेख सबसे कुशल पथ को निर्धारित करने के लिए Dijkstra के एल्गोरिदम का उपयोग करके गणना करने के तरीके का एक चरण-दर-चरण अवलोकन प्रदान करता है।

अल्गोरिथम को समझना

एल्गोरिथ्म, सबसे छोटी अस्थायी दूरी के साथ नोड का चयन करके काम करता है, फिर अपने पड़ोसी नोड्स की दूरी को अद्यतन करता है। यह तब तक जारी रहता है जब तक कि लक्ष्य नोड के लिए सबसे कम पथ पाया जाता है या सभी नोड संसाधित किए गए हैं।

चरण-दर-चरण गणना प्रक्रिया

मान लीजिए कि हमारे पास नोड्स A, B, C, D और E, और निम्नलिखित भारित किनारों के साथ एक ग्राफ है:

  • A to B: 4
  • A to C: 2
  • B to C: 1
  • B to D: 5
  • C से D: 8
  • C से E: 10
  • D to E: 2

नोड A से शुरू होकर, दूरी शुरू करना: A = 0, अन्य = अनंतता। सभी नोड्स को अनिर्णित रूप में चिह्नित करें।

पुनरावृत्ति 1

नोड A (distance 0) का चयन करें। पड़ोसी नोड्स B और C को अपडेट करें:

B: 4 (A + 4), C: 2 (A + 2) के लिए दूरी। मार्क A का दौरा किया।

2

नोड C (distance 2) का चयन करें। पड़ोसियों D और E अद्यतन:

D: 10 (C + 8) की दूरी, E: 12 (C + 10)। मार्क C का दौरा किया।

3

नोड B (distance 4) का चयन करें। पड़ोसी D अद्यतन:

D: 9 (B + 5) की दूरी, जो पिछले 10 से कम है। D की दूरी 9 तक।

पुनरावृत्ति 4

नोड डी (distance 9) का चयन करें। पड़ोसी ई अद्यतन करें:

E: 11 (D + 2) की दूरी। E की दूरी 11 तक। मार्क D का दौरा किया।

5

शेष नोड ई में 11. मार्क ई की दूरी देखी गई है। A से E तक का सबसे छोटा पथ कुल दूरी 11. के साथ नोड्स C, B, D और E के माध्यम से है।