BFS लघुतम पथ की लंबाई

जब BFS एल्गोरिथ्म एक नोड (गांठ) से शुरू होता है और क्रमिक रूप से उसके पड़ोसी नोड्स तक फैलता जाता है, तो यह संभव हो जाता है कि हम शुरुआती नोड से लेकर अन्य सभी नोड्स तक का लघुतम पथ (Shortest Path) खोज सकें। इसके लिए हमें मूल एल्गोरिथ्म में थोड़ा संशोधन करना होगा। हम एक distance ऐरे d का उपयोग करेंगे, जिसकी सभी प्रविष्टियाँ शुरू में -1 पर सेट होंगी। अगर किसी वर्टेक्स (शीर्ष) का मान -1 है, तो इसका मतलब है कि वह वर्टेक्स अभी तक विज़िट (देखा) नहीं हुआ है। और अगर उसमें कोई धनात्मक मान है, तो वह प्रारंभिक बिंदु से उस वर्टेक्स तक की दूरी को दर्शाता है:

from collections import deque

n, e = map(int, input().split())        # n: वर्टिसेज (शीर्ष), e: ऐजेस (धारें)
g = [[] for _ in range(n)]              # ग्राफ - ऐडजेसंसी लिस्ट

for _ in range(e):                      # ऐजेस को पढ़ें
    a, b = map(int, input().split())    # a -> b और b -> a
    g[a].append(b)
    g[b].append(a)

start = int(input())                    # शुरुआती वर्टेक्स
d = [-1] * n                            # शुरुआती वर्टेक्स से दूरी
q = deque([start])                      # वर्टेक्स की कतार (queue)
d[start] = 0                            # स्टार्ट से स्टार्ट की दूरी 0

while q:                                # जब तक कतार खाली न हो
    v = q.popleft()                     # कतार से वर्टेक्स निकालें
    print(v, end=' ')                   # वर्टेक्स को प्रिंट करें
    for to in g[v]:                     # v से जुड़े प्रत्येक वर्टेक्स के लिए
        if d[to] == -1:                 # अगर वर्टेक्स अभी तक विज़िट नहीं हुआ
            d[to] = d[v] + 1            # (start -> to) = (start -> v) + 1
            q.append(to)                # उस वर्टेक्स को कतार में जोड़ें

print(d)

यहाँ हम सबसे पहले distance ऐरे d को -1 से इनिशियलाइज़ (शुरुआती मान) करते हैं। यह संकेत देता है कि अभी तक किसी भी वर्टेक्स का इस्तेमाल नहीं हुआ है। फिर हम d[start] का मान 0 सेट करते हैं, जिसका अर्थ है कि start वर्टेक्स से start वर्टेक्स तक की दूरी 0 है।

एल्गोरिथ्म जैसे-जैसे और नोड्स की प्रोसेसिंग करता है, वैसे-वैसे d ऐरे में उन नोड्स की दूरी के मान अपडेट होते रहते हैं। इस तरह, हमें start वर्टेक्स से निकलकर शेष सभी वर्टेक्स तक की दूरी मिल जाती है।

चलिए अब कुछ उदाहरणों पर एल्गोरिथ्म का सिमुलेशन करके देखते हैं:

n = 4, e = 4

इनपुट में दिए गए a, b पेयर्स इस प्रकार हैं: [(0, 1), (0, 2), (1, 2), (3, 2)]

शुरुआती वर्टेक्स है 3

d = [-1, -1, -1, 0], q = [3]

v = 3, q = [] → उन सभी पड़ोसियों को जोड़ें जो अभी तक उपयोग में नहीं आए

d = [-1, -1, 1, 0], q = [2]

v = 2, q = [] → उन सभी पड़ोसियों को जोड़ें जो अभी तक उपयोग में नहीं आए

d = [2, 2, 1, 0], q = [0, 1]

v = 0, q = [1] → उन सभी पड़ोसियों को जोड़ें जो अभी तक उपयोग में नहीं आए

v = 1, q = [] → उन सभी पड़ोसियों को जोड़ें जो अभी तक उपयोग में नहीं आए

पूरा हुआ

n = 5, e = 4

इनपुट में दिए गए a, b पेयर्स इस प्रकार हैं: [(0, 1), (0, 2), (1, 2), (3, 4)]

शुरुआती वर्टेक्स है 0

d = [0, -1, -1, -1, -1], q = [0]

v = 0, q = [] → उन सभी पड़ोसियों को जोड़ें जो अभी तक उपयोग में नहीं आए

d = [0, 1, 1, -1, -1], q = [1, 2]

v = 1, q = [2] → उन सभी पड़ोसियों को जोड़ें जो अभी तक उपयोग में नहीं आए

v = 2, q = [] → उन सभी पड़ोसियों को जोड़ें जो अभी तक उपयोग में नहीं आए

पूरा हुआ

Notice how nodes 3 and 4 were never visited.

They were not connected to the initial node 0.

चुनौती: लघुतम पथ की लंबाई खोजें

मान लीजिए कि आपके पास एक अविनिदेशित (undirected) ग्राफ है, जिसमें v वर्टिसेज और e ऐजेस हैं। आपको वर्टेक्स 1 और वर्टेक्स v के बीच का लघुतम पथ ढूँढना है। अगर ये दोनों जुड़े हुए नहीं हैं, तो प्रोग्राम को "Impossible" प्रिंट करना चाहिए।

इनपुट

इनपुट की पहली पंक्ति में दो पूर्णांक v (1 ≤ v ≤ 100000) और e (1 ≤ e ≤ 100000) दिए जाते हैं।

इसके बाद की e पंक्तियों में प्रत्येक में v1, v2 (1 ≤ v1, v2 ≤ v) की एक जोड़ी होती है, जो दर्शाती है कि वर्टेक्स v1 वर्टेक्स v2 से और v2 वर्टेक्स v1 से जुड़ा हुआ है।

आउटपुट

प्रोग्राम को वर्टेक्स 1 और वर्टेक्स v के बीच के लघुतम पथ की लंबाई प्रिंट करनी है।

उदाहरण

Input	Input
5 6 1 2 2 3 1 3 3 4 4 3 3 5	2
2 1 1 2	1
2 0	Impossible

चुनौती: लघुतम पथ की लंबाई खोजें

इनपुट

आउटपुट

उदाहरण

Constraints

To check your solution you need to sign in

Sign in to continue