कोडिंग इंटरव्यू: Dijkstra का सबसे छोटा पथ (Shortest Path) एल्गोरिदम लागू करना

समस्या विवरण और दायरा

आपको n नोड्स वाला एक निर्देशित ग्राफ़ दिया गया है, जिन्हें 0 से n - 1 तक लेबल किया गया है। प्रत्येक एज एक टपल (from, to, weight) है। source और target दिए जाने पर, स्रोत से लक्ष्य तक सबसे छोटी दूरी और एक सबसे छोटा पथ शामिल करने वाला युग्म (pair) लौटाएं। जब लक्ष्य तक पहुंचना असंभव हो तो (-1, []) लौटाएं।

इस संस्करण के लिए, मान लें कि 1 <= n <= 100000, 0 <= m <= 300000, प्रत्येक नोड लेबल मान्य है, और 0 <= weight <= 10^9 है। समानांतर एज (parallel edges), शून्य-भार वाली एज (zero-weight edges), और सेल्फ-लूप (self-loops) की अनुमति है। source और target मान्य लेबल हैं। यदि वे समान हैं, तो (0, [source]) लौटाएं। जब कई पथों की दूरी समान हो, तो कोई भी सबसे छोटा पथ स्वीकार्य है।

उदाहरण के लिए, एज (0, 1, 4), (0, 2, 1), (2, 1, 2), (1, 3, 1), (2, 3, 5), (3, 4, 3), और (2, 4, 12) के साथ, 0 से 4 तक का उत्तर दूरी 7 और पथ [0, 2, 1, 3, 4] है।

गैर-ऋणात्मक भार की स्थिति एल्गोरिदम अनुबंध (contract) का एक हिस्सा है। एक भारित (weighted) ग्राफ़ का अपने आप में यह अर्थ नहीं है कि Dijkstra का ही उपयोग किया जाए: एक भारहीन (unweighted) ग्राफ़ BFS को प्राथमिकता देता है, एक DAG टोपोलॉजिकल डायनामिक प्रोग्रामिंग का उपयोग कर सकता है, और नकारात्मक एज वाले सामान्य ग्राफ़ के लिए Bellman-Ford जैसे एल्गोरिदम की आवश्यकता होती है।

साक्षात्कारकर्ता क्या मूल्यांकन करता है

पहला संकेत अनुबंध के आधार पर एल्गोरिदम का चयन है। Dijkstra उपयुक्त है क्योंकि एज भार गैर-ऋणात्मक हैं और केवल एक स्रोत शामिल है। एक उम्मीदवार जो नकारात्मक भार के बारे में पूछे बिना कहता है कि "भारित ग्राफ़ का मतलब Dijkstra है", वह निर्णायक पूर्व-शर्त (precondition) से चूक गया है।

दूसरा संकेत डेटा संरचना का इनवेरिएंट (data structure invariant) है। एक adjacency matrix को O(V^2) स्पेस की आवश्यकता होगी, जो 100,000 नोड्स तक के लिए अनुपयुक्त है। एक adjacency list केवल वही V + E जानकारी संग्रहीत करती है जिसका उपयोग ट्रैवर्सल करता है। एक min-heap उस अनिर्धारित (unsettled) नोड को पुनः प्राप्त करता है जिसकी खोजी गई दूरी सबसे कम है।

तीसरा संकेत यह है कि दूरी में कमी को कैसे दर्शाया जाता है। Python का heapq किसी मनमाने आइटम को इन-प्लेस अपडेट नहीं करता है। व्यावहारिक समाधान एक नया (distance, node) युग्म पुश करना है और बाद में एक पुराने युग्म को छोड़ देना है जब उसकी दूरी अब distances[node] के बराबर नहीं रहती। इस लेज़ी-डिलीशन (lazy-deletion) विवरण को छोड़ना आसान है, और यह शुद्धता के तर्क तथा सटीक जटिलता सीमा दोनों को बदल देता है।

साक्षात्कारकर्ता केवल काम करने वाले कोड की नहीं, बल्कि प्रमाण की भी अपेक्षा करता है। एक मजबूत उत्तर बताता है कि किसी नोड के लिए पॉप की गई पहली वर्तमान प्रविष्टि अंतिम क्यों है, गैर-ऋणात्मक भार उस लालची (greedy) कदम को सुरक्षित क्यों बनाते हैं, और लक्ष्य को पहली बार खोजे जाने के बजाय उसके पॉप होने पर क्यों लौटाया जा सकता है। पथ पुनर्निर्माण (path reconstruction), पहुंच से बाहर इनपुट, शून्य-भार वाली एज, समानांतर एज, पूर्णांक चौड़ाई (integer width), और प्रतिकूल परीक्षण (adversarial tests) उत्तर को पूरा करते हैं।

उत्तर देने से पहले स्पष्ट करने वाले प्रश्न

• क्या एज भार ऋणात्मक हो सकते हैं? मूल समस्या कहती है कि नहीं। यदि ऋणात्मक एज की अनुमति है,

तो Dijkstra का सेटलिंग प्रमाण और प्रारंभिक निकास (early exit) लागू नहीं होते।

• क्या ग्राफ़ निर्देशित है? हाँ। अप्रत्यक्ष (undirected) ग्राफ़ के लिए, adjacency list में दोनों दिशाएँ जोड़ें।
• क्या हमें केवल दूरी की आवश्यकता है या पथ की भी? इस संस्करण को दोनों की आवश्यकता है, इसलिए जब भी रिलैक्सेशन

दूरी में स्पष्ट सुधार करता है, तो एक पूर्ववर्ती (predecessor) को संग्रहीत करें।

• क्या समानांतर एज, शून्य-भार वाली एज, या सेल्फ-लूप हो सकते हैं? हाँ। रिलैक्सेशन बिना किसी प्रीप्रोसेसिंग के

उन्हें संभालता है। एक गैर-ऋणात्मक सेल्फ-लूप अपने स्वयं के नोड में सुधार नहीं कर सकता।

• पहुंच से बाहर (unreachable) का क्या अर्थ होना चाहिए? (-1, []) लौटाएं; इसे शून्य-लंबाई वाले पथ के साथ भ्रमित न करें।
• जब कई सबसे छोटे पथ मौजूद हों, तो क्या कोई भी स्वीकार्य है? हाँ। कार्यान्वयन केवल स्पष्ट सुधार पर ही एक

पूर्ववर्ती को अपडेट करता है, इसलिए समान विकल्प पथ ट्री को अस्थिर नहीं करते हैं।

• दूरी कितनी बड़ी हो सकती है? एक सरल सबसे छोटे पथ में अधिकतम n - 1 एज होती हैं, इसलिए बताई गई

सीमाओं के तहत यह 10^14 से कम है। Python पूर्णांक असीमित हैं; एक निश्चित चौड़ाई वाली भाषा में 64-बिट पूर्णांक का उपयोग करें।

30-सेकंड का उत्तर ढांचा (Framework)

"मैं एक adjacency list बनाऊंगा और distances[v] बनाए रखूंगा, जो अब तक खोजी गई सर्वोत्तम स्रोत-से-v दूरी है। मैं स्रोत को शून्य पर इनिशियलाइज़ करता हूँ और (0, source) को एक min-heap में रखता हूँ। हर बार जब मैं सबसे छोटी प्रविष्टि निकालता हूँ, तो यदि वह पुरानी (stale) है तो मैं उसे छोड़ देता हूँ। अन्यथा उस नोड की दूरी अंतिम है क्योंकि शेष प्रत्येक एज का भार गैर-ऋणात्मक है। मैं प्रत्येक आउटगोइंग एज को रिलैक्स करता हूँ और प्रत्येक स्पष्ट सुधार के लिए एक नई हीप प्रविष्टि पुश करता हूँ, पथ पुनर्निर्माण के लिए एक पूर्ववर्ती को रिकॉर्ड करता हूँ। जब लक्ष्य की वर्तमान प्रविष्टि पॉप हो जाती है तो मैं रुक सकता हूँ। यदि इसकी दूरी अनंत रहती है, तो मैं (-1, []) लौटाता हूँ; अन्यथा मैं पूर्ववर्तियों का पीछे की ओर अनुसरण करता हूँ और पथ को उलट देता हूँ। लेज़ी हीप प्रविष्टियों के साथ, समय O((V + E) log E) है और स्पेस O(V + E) है।"

चरण-दर-चरण विस्तृत विवरण

एक खोजे गए मार्ग को एक सिद्ध सबसे छोटे मार्ग से अलग करके शुरुआत करें। distances[v] वास्तविक सबसे छोटी दूरी पर एक ऊपरी सीमा है क्योंकि यह या तो अनंत है या पहले से मिले वास्तविक मार्ग की लंबाई है। भार w वाली एक एज u -> v को रिलैक्स करने से यह परीक्षण होता है कि क्या u के माध्यम से मार्ग बेहतर है: distances[u] + w < distances[v]। एक स्पष्ट सुधार दूरी और previous[v] दोनों को अपडेट करता है।

हीप में एक ही नोड के लिए कई प्रविष्टियाँ हो सकती हैं। उदाहरण में, एज 0 -> 1 पहले दूरी 4 सम्मिलित करती है। नोड 2 के संसाधित होने के बाद, मार्ग 0 -> 2 -> 1 नोड 1 को दूरी 3 में सुधारता है और एक दूसरी प्रविष्टि सम्मिलित करता है। जब अंततः (4, 1) पॉप किया जाता है, तो 4 != distances[1] होता है, इसलिए यह पुराना है और इसे अनदेखा किया जाना चाहिए। किसी स्पष्ट हीप-आइटम विलोपन या नोड-विज़िटेड सेट की आवश्यकता नहीं है।

from heapq import heappop, heappush


def shortest_path(
    n: int,
    edges: list[tuple[int, int, int]],
    source: int,
    target: int,
) -> tuple[int, list[int]]:
    graph: list[list[tuple[int, int]]] = [[] for _ in range(n)]
    for node, neighbor, weight in edges:
        if weight < 0:
            raise ValueError("Dijkstra requires non-negative edge weights")
        graph[node].append((neighbor, weight))

    distances = [float("inf")] * n
    previous = [-1] * n
    distances[source] = 0
    heap: list[tuple[int, int]] = [(0, source)]

    while heap:
        distance, node = heappop(heap)
        if distance != distances[node]:
            continue
        if node == target:
            break

        for neighbor, weight in graph[node]:
            candidate = distance + weight
            if candidate < distances[neighbor]:
                distances[neighbor] = candidate
                previous[neighbor] = node
                heappush(heap, (candidate, neighbor))

    if distances[target] == float("inf"):
        return -1, []

    path = []
    node = target
    while node != -1:
        path.append(node)
        node = previous[node]
    path.reverse()
    return int(distances[target]), path

शुद्धता के तर्क के दो भाग हैं। पहला, distances में प्रत्येक सीमित मान एक वास्तविक खोजे गए पथ की लंबाई है, इसलिए यह वास्तविक सबसे छोटे पथ की दूरी से छोटा नहीं हो सकता। दूसरा, मान लीजिए कि u के लिए एक वर्तमान प्रविष्टि पॉप की गई है लेकिन u के लिए एक छोटा पथ मौजूद है। उस पथ पर, पहला नोड लें जो अभी तक तय (settled) नहीं हुआ है और उसके पूर्ववर्ती को x कहें। नोड x पहले तय किया गया था, इसलिए इसकी आउटगोइंग एज को रिलैक्स किया गया था। इसलिए पहले अनिर्धारित नोड को u के काल्पनिक छोटे पथ की लंबाई से अधिक नहीं वाली एक हीप की (key) प्राप्त हुई थी। चूंकि सभी शेष एज भार गैर-ऋणात्मक हैं, इसलिए वह की u के लिए पॉप की गई की से छोटी है और इसे पहले पॉप किया जाना चाहिए था—जो कि एक विरोधाभास है। इस प्रकार पॉप की गई वर्तमान दूरी अंतिम है।

यह प्रमाण सुरक्षित प्रारंभिक निकास बिंदु (early-exit point) को भी परिभाषित करता है। लक्ष्य के एक वर्तमान, गैर-पुराने दूरी के साथ पॉप होने के बाद ही रुकें। जब कोई एज पहली बार लक्ष्य की खोज करती है तो न रुकें: बाद का मार्ग इसमें सुधार कर सकता है। नमूना ग्राफ़ के लिए, नोड 4 की प्रत्यक्ष खोज की लागत 13 है, जबकि अंतिम मार्ग की लागत 7 है।

previous[v] = u वर्तमान में v के लिए सर्वश्रेष्ठ पथ की अंतिम एज को रिकॉर्ड करता है। एक बार जब लक्ष्य की दूरी अंतिम हो जाती है, तो पूर्ववर्तियों का अनुसरण करने पर स्रोत तक पहुंचना अनिवार्य है क्योंकि प्रत्येक पूर्ववर्ती असाइनमेंट एक वास्तविक स्रोत-आधारित मार्ग से आया था। उस श्रृंखला को उलटने पर पथ आगे के क्रम में प्राप्त होता है। जब स्रोत लक्ष्य के बराबर होता है, तो स्रोत तुरंत पॉप हो जाता है और पुनर्निर्माण [source] लौटाता है।

Adjacency list के निर्माण में O(V + E) स्पेस और O(E) समय लगता है। प्रत्येक सफल रिलैक्सेशन एक हीप प्रविष्टि को पुश करता है, इसलिए प्रारंभिक स्रोत प्रविष्टि के अलावा अधिकतम E ऐसे पुश होते हैं। लेज़ी डुप्लिकेट के साथ, हीप में O(E) प्रविष्टियाँ हो सकती हैं, जिससे O((V + E) log E) समय और O(V + E) कुल स्पेस प्राप्त होता है। पाठ्यपुस्तकें अक्सर decrease-key का समर्थन करने वाले हीप के लिए O((V + E) log V) बताती हैं, या सरल विरल ग्राफ़ (sparse graphs) के लिए उस सीमा तक सरल बनाती हैं। लेज़ी कार्यान्वयन की log E सीमा का उल्लेख करना अधिक सटीक है।

केवल सामान्य पथ (happy path) का ही नहीं, बल्कि अनुबंध का परीक्षण करें। नमूने को (7, [0, 2, 1, 3, 4]) लौटाना चाहिए। समानांतर एज और एक शून्य भार—(0, 1, 10), (0, 1, 2), (1, 2, 0)—को (2, [0, 1, 2]) लौटाना चाहिए। इसके अलावा एक अगम्य लक्ष्य, लक्ष्य के बराबर स्रोत, एक सेल्फ-लूप, समान लागत वाले विकल्प और शून्य भार वाली एज का परीक्षण करें। एक नकारात्मक एज को टूटी हुई पूर्व-शर्त के तहत चुपचाप उत्तर देने के बजाय स्पष्ट त्रुटि उत्पन्न करनी चाहिए।

एक छोटा सा विभेदक परीक्षण (differential test) गैर-ऋणात्मक ग्राफ़ उत्पन्न कर सकता है, प्रत्येक स्रोत से इस फ़ंक्शन को चला सकता है, और Bellman-Ford के साथ इसकी दूरियों की तुलना कर सकता है। लौटाए गए पथों के लिए, पहले और अंतिम नोड को सत्यापित करें, सत्यापित करें कि प्रत्येक लगातार युग्म एक इनपुट एज है, और चयनित एज भार का योग करें। समानांतर एज के साथ, परीक्षण को प्रत्येक नोड युग्म में एक एज होने का अनुमान लगाने के बजाय पथ चरण को एक मिलान वाले एज भार के साथ जोड़ना चाहिए।

उच्च-गुणवत्ता वाला नमूना उत्तर

"मैं पहले पुष्टि करूंगा कि सभी एज भार गैर-ऋणात्मक हैं, ग्राफ़ निर्देशित है, और कोई भी सबसे छोटा पथ स्वीकार्य है। वे स्थितियाँ मुझे Dijkstra का उपयोग करने की अनुमति देती हैं। मैं आउटगोइंग एज को एक adjacency list में संग्रहीत करूंगा क्योंकि ग्राफ़ में 100,000 नोड्स और 300,000 एज हो सकती हैं; एक adjacency matrix बहुत बड़ा होगा।

distances[v] स्रोत को छोड़कर अनंत से शुरू होता है, जो शून्य से शुरू होता है। एक min-heap खोजे गए (distance, node) युग्मों को संग्रहीत करता है। जब मुझे वर्तमान नोड के माध्यम से एक छोटा मार्ग मिलता है, तो मैं पड़ोसी की दूरी और पूर्ववर्ती को अपडेट करता हूँ और एक नया युग्म पुश करता हूँ। चूंकि heapq में कोई मनमाना decrease-key नहीं है, इसलिए पुराने युग्म हीप में बने रहते हैं। मैं पॉप की गई दूरी की तुलना वर्तमान सरणी मान से करके उनका पता लगाता हूँ और किसी भी बेमेल को छोड़ देता हूँ।

मुख्य प्रमाण सेटलिंग इनवेरिएंट (settling invariant) है। जब नोड u के लिए एक वर्तमान प्रविष्टि हीप न्यूनतम होती है, तो किसी भी काल्पनिक छोटे मार्ग में एक पहला अनिर्धारित नोड होगा जिसका पूर्ववर्ती पहले से ही तय किया जा चुका था। उस पूर्ववर्ती के रिलैक्सेशन ने हीप में एक समान या छोटी उपसर्ग दूरी (prefix distance) रखी होगी। गैर-ऋणात्मक शेष भार का अर्थ है कि उस उपसर्ग को u से पहले पॉप किया जाना चाहिए था, जो कि एक विरोधाभास है। इसलिए u अंतिम है। यही कारण है कि लक्ष्य की वर्तमान प्रविष्टि पॉप होने पर मैं रुक सकता हूँ, लेकिन लक्ष्य को पहली बार देखे जाने पर नहीं।

यदि लक्ष्य अनंत रहता है, तो मैं (-1, []) लौटाता हूँ। अन्यथा मैं लक्ष्य से स्रोत तक पूर्ववर्ती पॉइंटर्स का अनुसरण करता हूँ और उन्हें उलट देता हूँ। प्रत्येक सफल रिलैक्सेशन अधिकतम एक नई हीप प्रविष्टि बनाता है, इसलिए यह लेज़ी कार्यान्वयन O((V + E) log E) समय में चलता है और O(V + E) स्पेस का उपयोग करता है। एक निश्चित चौड़ाई वाली भाषा में मैं 64-बिट दूरियों का उपयोग करूंगा। मैं पुरानी प्रविष्टियों, समानांतर और शून्य-भार वाली एज, समान लागत वाले पथ, लक्ष्य के बराबर स्रोत, अगम्य इनपुट, और नकारात्मक एज की अस्वीकृति का परीक्षण करूंगा।"

सामान्य गलतियाँ

• नकारात्मक भार के बारे में पूछे बिना Dijkstra चलाना → लालची अंतिमीकरण प्रमाण विफल हो जाता है →

गैर-ऋणात्मक भार को एक स्पष्ट पूर्व-शर्त बनाएं और अमान्य इनपुट को अस्वीकार करें।

• लक्ष्य के पहली बार रिलैक्स होने पर रुक जाना → पहला खोजा गया मार्ग महंगा हो सकता है →

केवल तभी रुकें जब लक्ष्य की वर्तमान हीप प्रविष्टि पॉप हो जाए।

• पुरानी हीप प्रविष्टियों को प्रोसेस करना → पुरानी दूरियाँ आउटगोइंग एज को बार-बार स्कैन करती हैं → **जब

distance != distances[node] हो तो छोड़ दें।**

• नोड को पहली बार पुश किए जाने पर विज़िट किया गया चिह्नित करना → बाद का एक छोटा मार्ग दब जाता है → **एक नोड

तभी तय होता है जब उसकी वर्तमान न्यूनतम प्रविष्टि पॉप हो जाती है।**

• Adjacency matrix का उपयोग करना → विरल इनपुट O(V^2) मेमोरी की खपत करता है → **O(V + E) स्टोरेज वाली

adjacency list का उपयोग करें।**

• समान दूरी पर बिना किसी टाई नियम के पूर्ववर्तियों को अपडेट करना → शून्य-भार वाले चक्र पथ

विकल्पों को अस्थिर कर सकते हैं → जब कोई भी सबसे छोटा पथ स्वीकार्य हो तो सख्त सुधार (strict improvement) का उपयोग करें।

• एक सीमित दूरी लौटाना लेकिन कोई पथ अनुबंध नहीं → कार्यान्वयन संकेत को संतुष्ट नहीं कर सकता

→ प्रत्येक सख्त सुधार पर एक पूर्ववर्ती रिकॉर्ड करें और खोज के बाद पुनर्निर्माण करें।

• बिना किसी योग्यता के इस हीप कार्यान्वयन को O(E log V) कहना → लेज़ी डुप्लिकेट

हीप के आकार को E के समानुपाती बना सकते हैं → O((V + E) log E) बताएं, फिर पारंपरिक decrease-key सीमा की व्याख्या करें।

• 32-बिट दूरी का उपयोग करना → पथ लगभग 2.1 बिलियन से अधिक हो सकते हैं → **Python पूर्णांक या 64-बिट

प्रकार का उपयोग करें।**

• केवल अंतिम दूरी का परीक्षण करना → एक विकृत पूर्ववर्ती श्रृंखला पर किसी का ध्यान नहीं जाता → **पथ के

अंतिम बिंदुओं, एज और जोड़े गए भार को भी मान्य करें।**

फॉलो-अप और उन्हें कैसे संभालें

फॉलो-अप 1: यदि केवल दूरी की आवश्यकता हो तो क्या बदलता है?

previous सरणी और पथ पुनर्निर्माण को हटा दें। खोज, प्रमाण और स्पर्शोन्मुख सीमाएं (asymptotic bounds) समान रहती हैं, हालांकि सहायक नोड स्टोरेज एक O(V) सरणी से कम हो जाती है। लक्ष्य के वर्तमान पॉप पर प्रारंभिक निकास सुरक्षित रहता है।

फॉलो-अप 2: क्या होगा यदि हमें प्रत्येक स्रोत से सबसे छोटी दूरी की आवश्यकता हो?

प्रत्येक नोड से Dijkstra को चलाने में इस कार्यान्वयन के साथ O(V(V + E) log E) की लागत आती है। एक घने (dense) ग्राफ़ के लिए, Floyd-Warshall O(V^3) समय और O(V^2) स्पेस का उपयोग करता है और नकारात्मक चक्र न होने पर नकारात्मक एज को भी संभालता है। Johnson का एल्गोरिदम नकारात्मक एज वाले लेकिन बिना नकारात्मक चक्र वाले विरल ग्राफ़ के लिए रीवेटिंग (reweighting) को बार-बार Dijkstra के साथ जोड़ता है। वास्तविक ग्राफ़ घनत्व और क्वेरी वॉल्यूम के आधार पर चुनें।

फॉलो-अप 3: क्या होगा यदि नकारात्मक एज की अनुमति हो?

एक सामान्य निर्देशित ग्राफ़ के लिए Bellman-Ford का उपयोग करें। यह बार-बार सभी एज को रिलैक्स करता है, O(VE) में चलता है, और एक और सफल रिलैक्सेशन एक पहुंच योग्य नकारात्मक चक्र का पता लगाता है। प्रति-उदाहरण 0 -> 1 = 2, 0 -> 2 = 5, 2 -> 1 = -10 इस मुद्दे को दर्शाता है: प्रारंभिक-निकास Dijkstra लक्ष्य 1 को 2 पर तय करता है, लेकिन नोड 2 के माध्यम से वास्तविक मार्ग की लागत -5 है।

फॉलो-अप 4: क्या होगा यदि ग्राफ़ एक DAG है और कुछ एज नकारात्मक हैं?

DAG को टोपोलॉजिकल रूप से सॉर्ट करें, फिर टोपोलॉजिकल क्रम में आउटगोइंग एज को एक बार रिलैक्स करें। प्रत्येक पूर्ववर्ती को उसके उत्तराधिकारी से पहले संसाधित किया जाता है, इसलिए नकारात्मक भार सुरक्षित हैं और कुल समय O(V + E) है। यह मजबूत गैर-चक्रीय अनुबंध के तहत Bellman-Ford और Dijkstra को पीछे छोड़ देता है।

फॉलो-अप 5: क्या होगा यदि प्रत्येक भार या तो 0 या 1 है?

एक deque के साथ 0-1 BFS का उपयोग करें। शून्य-भार वाले रिलैक्सेशन को आगे और एक-भार वाले रिलैक्सेशन को पीछे पुश करें। Deque गैर-घटते दूरी क्रम को सुरक्षित रखता है, जिससे बिना किसी हीप के O(V + E) समय मिलता है।

फॉलो-अप 6: बार-बार एज अपडेट होने पर डिज़ाइन कैसे बदलेगा?

कभी-कभार होने वाले अपडेट के लिए, adjacency list को फिर से बनाएं या प्रभावित एज को बदलें और Dijkstra को फिर से चलाएं; सरल समाधान को सत्यापित करना सबसे आसान है। सख्त विलंबता आवश्यकताओं के साथ बार-बार होने वाले अपडेट के लिए अमान्यकरण (invalidation) के साथ डायनामिक सबसे छोटे पथ की तकनीकों या कैश्ड स्रोत ट्री की आवश्यकता होती है, जिसका मूल्य अपडेट/क्वेरी अनुपात और ग्राफ़ संरचना पर निर्भर करता है। यह दावा न करें कि एक स्थानीय एज परिवर्तन केवल उसके दो समापन बिंदुओं को प्रभावित करता है।

फॉलो-अप 7: आप लेक्सिकोग्राफ़िक रूप से सबसे छोटा पथ कैसे लौटाएंगे?

केवल सख्त दूरी की तुलना पर्याप्त नहीं है क्योंकि यह जानबूझकर पहले समान लागत वाले पथ को रखती है। पहले ऑर्डरिंग अनुबंध को परिभाषित करें। एक दृष्टिकोण सबसे छोटी दूरियों की गणना करता है, उम्मीदवार परिवर्तनों को उन दूरियों के अनुरूप एज तक सीमित करता है, और फिर लक्ष्य तक पहुंच सुनिश्चित करते हुए सबसे छोटे मान्य अगले नोड का चयन करता है। शून्य-भार वाले चक्रों के लिए चक्र-जागरूक (cycle-aware) हैंडलिंग की आवश्यकता होती है। प्रत्येक हीप प्रविष्टि के अंदर पूर्ण पथ टपल्स की तुलना करना छोटे इनपुट के लिए सरल है लेकिन पर्याप्त कॉपी और तुलना लागत जोड़ सकता है।