नेटवर्क विलंब समय और पथ पुनर्निर्माण
Dijkstra से network-delay-time हल कीजिए, पूर्ववर्ती मैप का उपयोग करके वास्तविक सबसे छोटा पथ पुनर्निर्मित कीजिए और बड़े ग्राफ़ के लिए द्विदिश BFS पर चर्चा कीजिए।
नेटवर्क विलंब समय और पथ पुनर्निर्माण, CoddyKit पर कोडिंग साक्षात्कार की तैयारी का एक निःशुल्क पाठ है। यह 4 में से 4वाँ पाठ है। आप नीचे पूरा पाठ निःशुल्क पढ़ सकते हैं—फिर अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर के साथ ब्राउज़र में इसका व्यावहारिक अभ्यास कर सकते हैं। यह कोडिंग साक्षात्कार की तैयारी सीखने के मार्ग का हिस्सा है और आपकी प्रगति वेब तथा CoddyKit ऐप पर सिंक होती रहती है। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
नेटवर्क विलंब समय की समस्या
नेटवर्क विलंब समय (LeetCode 743): n नोड वाले नेटवर्क और सिग्नल के यात्रा-समय दर्शाने वाले दिशित भारित किनारों को देखते हुए, यह ज्ञात करें कि नोड k से भेजे गए सिग्नल को सभी नोडों तक पहुँचने में न्यूनतम कितना समय लगेगा। यदि कोई नोड पहुँच से बाहर हो, तो -1 लौटाएँ। यह Dijkstra का सीधा अनुप्रयोग है: उत्तर, k से सभी नोडों तक की सबसे छोटी-पथ दूरियों में से अधिकतम दूरी है।
समाधान: Dijkstra + दूरियों में अधिकतम
सभी नोडों v के लिए dist[v] निकालने हेतु स्रोत k से Dijkstra चलाएँ। उत्तर max(dist.values()) है। यदि कोई dist[v] अभी भी inf है, तो वह नोड पहुँच से बाहर है — -1 लौटाएँ। सिग्नल सभी पथों पर एक साथ चलता है, इसलिए सबसे बड़ी बाधा वह नोड है जहाँ पहुँचने में सबसे अधिक समय लगता है।
import heapq
from collections import defaultdict
def networkDelayTime(times, n, k):
graph = defaultdict(list)
for u, v, w in times:
graph[u].append((v, w))
dist = {i: float('inf') for i in range(1, n+1)}
dist[k] = 0
heap = [(0, k)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(heap, (dist[v], v))
ans = max(dist.values())
return ans if ans < float('inf') else -1
print(networkDelayTime([[2,1,1],[2,3,1],[3,4,1]], 4, 2)) # 2prev सारणी से पथ का पुनर्निर्माण
दूरियाँ निकालने के साथ-साथ वास्तविक सबसे छोटे पथ का पुनर्निर्माण करने के लिए एक prev शब्दकोश रखें, जो प्रत्येक नोड के लिए सबसे अच्छे पूर्ववर्ती नोड को दर्ज करे। जब भी हम dist[v] को अपडेट करें, prev[v] = u सेट करें। Dijkstra पूरा होने के बाद, गंतव्य से prev संकेतकों के माध्यम से पीछे की ओर चलते हुए स्रोत तक पहुँचें, फिर क्रम उलटकर आगे की दिशा वाला पथ प्राप्त करें।
import heapq
from collections import defaultdict
def shortest_path_with_reconstruction(times, n, src, dst):
graph = defaultdict(list)
for u, v, w in times:
graph[u].append((v, w))
dist = {i: float('inf') for i in range(1, n+1)}
prev = {i: None for i in range(1, n+1)}
dist[src] = 0
heap = [(0, src)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]: continue
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
prev[v] = u
heapq.heappush(heap, (dist[v], v))
# Reconstruct path from src to dst
path, node = [], dst
while node is not None:
path.append(node)
node = prev[node]
return dist[dst], path[::-1]बड़े अभारित ग्राफ के लिए द्विदिश BFS
बड़े अभारित ग्राफ में, जहाँ केवल एक स्रोत-गंतव्य युग्म की आवश्यकता हो, द्विदिश BFS सामान्य BFS से काफी तेज़ हो सकता है। यह स्रोत और गंतव्य दोनों से एक साथ BFS चलाता है और दोनों खोज-सीमाओं के मिलने पर रुक जाता है। व्यावहारिक गति-वृद्धि महत्वपूर्ण होती है, क्योंकि प्रत्येक खोज-सीमा को ग्राफ की गहराई का केवल आधा भाग खोजना पड़ता है — इससे खोजे गए नोड O(b^d) से घटकर O(2 × b^(d/2)) हो जाते हैं, जहाँ b शाखा-गुणक है।
from collections import deque
def bidir_bfs(graph, src, dst):
if src == dst: return 0
front_q = deque([src]); front_visited = {src: 0}
back_q = deque([dst]); back_visited = {dst: 0}
def expand(queue, visited, other_visited):
node = queue.popleft()
for nxt in graph[node]:
if nxt not in visited:
visited[nxt] = visited[node] + 1
queue.append(nxt)
if nxt in other_visited:
return visited[nxt] + other_visited[nxt]
return -1
while front_q or back_q:
res = expand(front_q, front_visited, back_visited)
if res != -1: return res
res = expand(back_q, back_visited, front_visited)
if res != -1: return res
return -1कौन-सा एल्गोरिदम कब चुनें
निर्णय मार्गदर्शिका: अभारित ग्राफ, एकल युग्म → BFS या द्विदिश BFS। भारित, गैर-ऋणात्मक, एकल स्रोत → Dijkstra। भारित, संभवतः ऋणात्मक, एकल स्रोत → बेलमैन-फोर्ड। सभी युग्म → फ्लॉयड-वॉरशॉल (छोटे V के लिए) या V × Dijkstra (विरल ग्राफ के लिए)। सीमित छलांगें → सीमित चरणों वाला संशोधित बेलमैन-फोर्ड। साक्षात्कार में इस निर्णय का तर्क स्पष्ट रूप से बताने से आपकी एल्गोरिद्मिक परिपक्वता प्रदर्शित होती है।
सबसे कम पहुँचने योग्य पड़ोसियों वाले शहर को खोजें (LeetCode 1334)
भारित पथों वाले शहरों और एक distanceThreshold को देखते हुए, उस सीमा के भीतर सबसे कम अन्य शहरों से पहुँचने योग्य शहर खोजें (बराबरी होने पर बड़े शहर-सूचकांक को प्राथमिकता दें)। समाधान: फ्लॉयड-वॉरशॉल से सभी युग्मों के सबसे छोटे पथ निकालें, फिर प्रत्येक शहर के लिए गिनें कि सीमा के भीतर कितने अन्य शहर पहुँच योग्य हैं। न्यूनतम संख्या वाले शहर को लौटाएँ (बराबरी होने पर अधिकतम सूचकांक)।
def findTheCity(n, edges, distanceThreshold):
INF = float('inf')
dist = [[INF]*n for _ in range(n)]
for i in range(n): dist[i][i] = 0
for u, v, w in edges:
dist[u][v] = dist[v][u] = w
for k in range(n):
for i in range(n):
for j in range(n):
dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
best_city, best_count = -1, n
for city in range(n):
count = sum(1 for j in range(n) if j != city and dist[city][j] <= distanceThreshold)
if count <= best_count:
best_count = count
best_city = city
return best_city
print(findTheCity(4,[[0,1,3],[1,2,1],[1,3,4],[2,3,1]],4)) # 3भारित DAG में पथ
दिशित अचक्रीय ग्राफ (DAG) में सबसे छोटे (या सबसे लंबे) पथ टोपोलॉजिकल क्रमण + रिलैक्सेशन द्वारा O(V+E) में खोजे जा सकते हैं — यह Dijkstra से तेज़ है। नोडों को टोपोलॉजिकल क्रम में संसाधित करें; नोड u को संसाधित करते समय उसके सभी बाहर जाने वाले किनारों पर रिलैक्सेशन करें। सबसे लंबे पथों के लिए (जो परियोजना निर्धारण / महत्वपूर्ण पथ के लिए उपयोगी हैं), भारों का चिह्न बदलें या min को max से बदलें।
from collections import deque
def dag_shortest_path(V, edges, source):
graph = [[] for _ in range(V)]
in_degree = [0] * V
for u, v, w in edges:
graph[u].append((v, w))
in_degree[v] += 1
# Topological sort (Kahn's)
queue = deque(i for i in range(V) if in_degree[i] == 0)
topo = []
while queue:
node = queue.popleft(); topo.append(node)
for nxt, _ in graph[node]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0: queue.append(nxt)
# Relax in topological order
dist = [float('inf')] * V
dist[source] = 0
for u in topo:
if dist[u] != float('inf'):
for v, w in graph[u]:
dist[v] = min(dist[v], dist[u] + w)
return distबाधाओं वाली मैट्रिक्स में सबसे छोटा पथ
साक्षात्कार में पूछा जाने वाला एक सामान्य रूपांतर: ऐसे 2D ग्रिड में ऊपर-बाएँ से नीचे-दाएँ तक सबसे छोटा पथ खोजें, जहाँ कुछ सेल अवरुद्ध हो सकते हैं। यह अभारित BFS समस्या है (प्रत्येक कदम की लागत 1 है)। 4 दिशाओं में गति के साथ BFS का उपयोग करें और दोबारा जाने से बचने के लिए सेल को कतार में डालते समय ही देखे गए के रूप में चिह्नित करें, निकालते समय नहीं। यदि बाधाओं से होकर गुज़रना संभव हो (किसी लागत के साथ), तो 2D ग्रिड को भारित ग्राफ मानकर उस पर Dijkstra चलाएँ।
from collections import deque
def shortest_path_binary_matrix(grid):
n = len(grid)
if grid[0][0] == 1 or grid[n-1][n-1] == 1:
return -1
queue = deque([(0, 0, 1)]) # (row, col, distance)
visited = {(0, 0)}
dirs = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
while queue:
r, c, d = queue.popleft()
if r == n-1 and c == n-1:
return d
for dr, dc in dirs:
nr, nc = r+dr, c+dc
if 0<=nr<n and 0<=nc<n and grid[nr][nc]==0 and (nr,nc) not in visited:
visited.add((nr,nc))
queue.append((nr, nc, d+1))
return -1
print(shortest_path_binary_matrix([[0,0,0],[1,1,0],[1,1,0]])) # 4बहु-स्रोत BFS
जब कई शुरुआती बिंदु हों (जैसे ग्रिड में कई 'द्वार' या मानचित्र में कई मूल-बिंदु), तो बहु-स्रोत BFS चलाएँ: सभी स्रोतों को दूरी 0 के साथ एक ही समय पर कतार में डालें। इससे एक ही BFS चरण में निकटतम स्रोत से प्रत्येक सेल की सबसे छोटी दूरी निकलती है। यह तकनीक प्रत्येक स्रोत से अलग-अलग BFS चलाने की आवश्यकता समाप्त करती है और इसकी कुल जटिलता O(V+E) है।
एल्गोरिदम चयन का पुनरावलोकन
संक्षिप्त निर्णय-वृक्ष: एकल स्रोत, गैर-ऋणात्मक भार → Dijkstra O((V+E) log V)। एकल स्रोत, ऋणात्मक भार → बेलमैन-फोर्ड O(VE)। सभी युग्म, छोटा V → फ्लॉयड-वॉरशॉल O(V³)। DAG, किसी भी भार के साथ → टोपोलॉजिकल क्रमण + रिलैक्सेशन O(V+E)। अभारित → BFS O(V+E)। ग्रिड पथ → BFS (अभारित) या हीप के साथ Dijkstra (भारित)। इस सारणी को याद रखें — यह किसी भी सबसे छोटे पथ वाले साक्षात्कार में पूरक प्रश्नों के उत्तर देने में मदद करती है।
साक्षात्कार प्रश्नों में पथ खोजना
साक्षात्कार की कई समस्याओं में केवल लागत नहीं, बल्कि वास्तविक पथ पूछा जाता है। हमेशा स्पष्ट करें: क्या आपको पथ चाहिए या केवल दूरी? यदि पथ चाहिए, तो शुरुआत में ही एक prev शब्दकोश बनाएँ। सामान्य गलतियाँ हैं: अंतिम स्थिति के रूप में prev[source] = None को आरंभ करना भूल जाना और पुनर्निर्माण का क्रम गलत समझना (गंतव्य से स्रोत तक पीछे जाएँ, फिर क्रम उलटें)। बड़ी समस्याओं पर लागू करने से पहले 3–4 नोड वाले उदाहरणों में पथ पुनर्निर्माण का अभ्यास करें।
त्वरित जाँच
इस पाठ में सिखाई गई डेटा संरचनाएँ और एल्गोरिदम — कोडिंग साक्षात्कार की तैयारी से जुड़ी अवधारणाओं की अपनी समझ जाँचें।
पाठ का पुनरावलोकन
इस पाठ में आपने सीखा: Dijkstra के बाद max(dist.values()) से नेटवर्क विलंब समय का उत्तर मिलता है, जब भी dist[v] में सुधार होता है, तब अपडेट की गई prev सारणी का उपयोग पथ पुनर्निर्माण के लिए किया जाता है, और द्विदिश BFS एकल-युग्म अभारित सबसे छोटे पथों के लिए खोज-क्षेत्र को आधा कर सकता है। आगे हम टोपोलॉजिकल क्रमण के लिए कान के एल्गोरिदम के साथ ग्राफ के क्रम निर्धारण का अध्ययन करेंगे।
एआई शिक्षक के साथ कोडिंग साक्षात्कार की तैयारी सीखें — निःशुल्क
अपने ब्राउज़र में वास्तविक कोड लिखें और चलाएँ, चौबीसों घंटे एआई शिक्षक से तुरंत सहायता पाएँ, और वेब या ऐप पर वहीं से शुरू करें जहाँ आपने छोड़ा था।
- पाठ्यक्रम
- 90
- पाठ
- 360
अक्सर पूछे जाने वाले प्रश्न
क्या “नेटवर्क विलंब समय और पथ पुनर्निर्माण” पाठ निःशुल्क है?
हाँ—“नेटवर्क विलंब समय और पथ पुनर्निर्माण” का पूरा पाठ यहाँ वेब पर निःशुल्क पढ़ा जा सकता है। इंटरैक्टिव अभ्यास (अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर) करने और कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम का बाकी हिस्सा अनलॉक करने के लिए CoddyKit PRO लें। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
“नेटवर्क विलंब समय और पथ पुनर्निर्माण” में मैं क्या सीखूँगा?
Dijkstra से network-delay-time हल कीजिए, पूर्ववर्ती मैप का उपयोग करके वास्तविक सबसे छोटा पथ पुनर्निर्मित कीजिए और बड़े ग्राफ़ के लिए द्विदिश BFS पर चर्चा कीजिए। आप ब्राउज़र में सीधे चलाए जाने वाले व्यावहारिक कोड के साथ कोडिंग साक्षात्कार की तैयारी का अभ्यास करते हैं, और पाठ पूरा करते समय 24/7 एआई ट्यूटर आपके प्रश्नों के उत्तर देता है।
क्या कोडिंग साक्षात्कार की तैयारी शुरू करने के लिए मुझे किसी अनुभव की आवश्यकता है?
पहले के अनुभव की आवश्यकता नहीं है। CoddyKit पर कोडिंग साक्षात्कार की तैयारी शुरुआती से लेकर उन्नत शिक्षार्थियों तक सभी के लिए व्यवस्थित किया गया है, इसलिए आप यहीं से या शुरुआत से सीखना शुरू कर सकते हैं और अपनी गति से आगे बढ़ सकते हैं। यह 4 में से 4वाँ पाठ है।
“नेटवर्क विलंब समय और पथ पुनर्निर्माण” पाठ पूरा करने में कितना समय लगता है?
CoddyKit का अधिकांश पाठ लगभग 5–10 मिनट में पूरा हो जाता है। हर पाठ छोटा और संवादात्मक है, इसलिए आप लगातार प्रगति करते हैं और वेब या ऐप पर वहीं से सीखना जारी रख सकते हैं जहाँ आपने छोड़ा था।
क्या मैं इस कोडिंग साक्षात्कार की तैयारी पाठ में कोड लिख और चला सकता हूँ?
हाँ। हर कोडिंग साक्षात्कार की तैयारी पाठ में एक अंतर्निर्मित कोड संपादक शामिल है, जिससे आप सीधे अपने ब्राउज़र में वास्तविक कोड लिख और चला सकते हैं और तुरंत एआई प्रतिक्रिया पा सकते हैं—स्थानीय सेटअप की आवश्यकता नहीं है।
इस पाठ्यक्रम के सभी पाठ
- प्राथमिकता कतार के साथ Dijkstra एल्गोरिदम
- Bellman-Ford और ऋणात्मक चक्र
- Floyd-Warshall: सभी युग्मों के सबसे छोटे पथ
- नेटवर्क विलंब समय और पथ पुनर्निर्माण