algorithm
बेलमैन-फोर्ड एल्गोरिथम

टिप्पणियों

सिंगल सोर्स शॉर्ट पाथ एलगोरिदम (एक ग्राफ में एक नकारात्मक चक्र होता है)

इस उदाहरण को पढ़ने से पहले, किनारे-विश्राम पर एक संक्षिप्त विचार होना आवश्यक है। आप इसे यहाँ से सीख सकते हैं

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

इस एल्गोरिथ्म का विचार इस ग्राफ के सभी किनारों को एक-एक करके कुछ यादृच्छिक क्रम से गुजरना है। यह कोई भी यादृच्छिक क्रम हो सकता है। लेकिन आपको यह सुनिश्चित करना होगा कि अगर uv (जहां u और v एक ग्राफ में दो वर्टिकल हैं) आपके आदेशों में से एक है, तो u से v तक एक बढ़त होनी चाहिए। आमतौर पर इसे सीधे दिए गए इनपुट के क्रम से लिया जाता है। फिर से, कोई भी यादृच्छिक क्रम काम करेगा।

आदेश का चयन करने के बाद, हम किनारों को विश्राम सूत्र के अनुसार आराम देंगे। एक दिया बढ़त यूवी यू से करने के लिए वी छूट सूत्र है जाने के लिए:

if distance[u] + cost[u][v] < d[v]
    d[v] = d[u] + cost[u][v]

यही है, अगर स्रोत से किसी भी शीर्ष u की दूरी + बढ़त uv का वजन स्रोत से दूसरे शिखर v की दूरी से कम है, तो हम स्रोत से v की दूरी को अपडेट करते हैं। हमें किनारों पर (V-1) समय पर आराम करने की आवश्यकता है जहां V ग्राफ में किनारों की संख्या है। आप (V-1) क्यों पूछते हैं? हम इसे दूसरे उदाहरण में समझाएंगे। इसके अलावा, हम किसी भी शीर्ष के मूल शीर्ष का ट्रैक रखने जा रहे हैं, जब हम एक किनारे को आराम करते हैं, तो हम सेट करेंगे:

parent[v] = u

इसका मतलब है कि हमें यू के माध्यम से वी तक पहुंचने के लिए एक और छोटा रास्ता मिल गया है। हमें इसकी आवश्यकता बाद में स्रोत से सबसे छोटे मार्ग को नियत शीर्ष पर मुद्रित करने के लिए होगी।

आइए एक उदाहरण देखें। हमारे पास एक ग्राफ है:

हमने स्रोत शीर्ष के रूप में 1 का चयन किया है। हम स्रोत से सबसे छोटे मार्ग का पता लगाना चाहते हैं।

सबसे पहले, d [1] = 0 क्योंकि यह स्रोत है। और बाकी अनंत हैं , क्योंकि हम अभी तक उनकी दूरी नहीं जानते हैं।

हम इस क्रम में किनारों को आराम देंगे:

+--------+--------+--------+--------+--------+--------+--------+
| Serial |    1   |    2   |    3   |    4   |    5   |    6   |
+--------+--------+--------+--------+--------+--------+--------+
|  Edge  |  4->5  |  3->4  |  1->3  |  1->4  |  4->6  |  2->3  |
+--------+--------+--------+--------+--------+--------+--------+

आप अपनी इच्छानुसार कोई भी अनुक्रम ले सकते हैं। यदि हम किनारों को एक बार आराम देते हैं , तो हमें क्या मिलता है? हम स्रोत से उस दूरी के अन्य सभी छोरों से दूरी प्राप्त करते हैं जो अधिकतम 1 किनारे पर उपयोग करते हैं। अब आइए किनारों को आराम दें और d [] के मूल्यों को अपडेट करें। हमें मिला:

1. घ [4] + लागत [4] [5] = अनंत + 7 = अनंत। हम इसे अपडेट नहीं कर सकते।
2. d [२] + लागत [३] [४] = अनंत । हम इसे अपडेट नहीं कर सकते।
3. d [१] + लागत [१] [२] = ० + २ = २ < d [२] । अतः d [२] = २ । साथ ही अभिभावक [२] = १ ।
4. d [१] + लागत [१] [४] = ४ । तो d [4] = 4 < d [4] । जनक [४] = १ ।
5. d [४] + लागत [४] [६] = ९ । d [६] = ९ < d [६] । जनक [६] = ४ ।
6. d [२] + लागत [२] [२] = अनंत । हम इसे अपडेट नहीं कर सकते।

हम कुछ कोने अपडेट नहीं कर सके, क्योंकि d[u] + cost[u][v] < d[v] स्थिति मेल नहीं खाती थी। जैसा कि हमने पहले कहा है, हमने अधिकतम 1 किनारे का उपयोग करते हुए स्रोत से अन्य नोड्स के लिए मार्ग पाया।

हमारा दूसरा पुनरावृत्ति हमें 2 नोड्स का उपयोग करके पथ प्रदान करेगा। हमें मिला:

1. d [४] + लागत [४] [५] = १२ < d [५] । d [५] = १२ । जनक [५] = ४ ।
2. d [३] + लागत [३] [४] = १ < d [४] । d [४] = १ । जनक [४] = ३ ।
3. d [3] अपरिवर्तित रहता है।
4. d [4] अपरिवर्तित रहता है।
5. d [४] + लागत [४] [६] = ६ < d [६] । d [६] = ६ । जनक [६] = ४ ।
6. d [3] अपरिवर्तित रहता है।

हमारा ग्राफ ऐसा दिखेगा:

हमारा तीसरा पुनरावृत्ति केवल शीर्ष 5 को अपडेट करेगा, जहां d [5] 8 होगा। हमारा ग्राफ ऐसा दिखेगा:

इसके बाद कोई फर्क नहीं पड़ता कि हम कितने पुनरावृत्तियों करते हैं, हमारे पास समान दूरी होगी। इसलिए हम एक ध्वज रखेंगे जो यह जांचता है कि कोई अपडेट हुआ या नहीं। यदि ऐसा नहीं होता है, तो हम बस लूप तोड़ देंगे। हमारा छद्म कोड होगा:

Procedure Bellman-Ford(Graph, source):
n := number of vertices in Graph
for i from 1 to n
    d[i] := infinity
    parent[i] := NULL
end for
d[source] := 0
for i from 1 to n-1
    flag := false
    for all edges from (u,v) in Graph
        if d[u] + cost[u][v] < d[v]
            d[v] := d[u] + cost[u][v]
            parent[v] := u
            flag := true
        end if
    end for
    if flag == false
        break
end for
Return d

नकारात्मक चक्र का ट्रैक रखने के लिए, हम यहां वर्णित प्रक्रिया का उपयोग करके अपने कोड को संशोधित कर सकते हैं । हमारा पूरा छद्म कोड होगा:

Procedure Bellman-Ford-With-Negative-Cycle-Detection(Graph, source):
n := number of vertices in Graph
for i from 1 to n
    d[i] := infinity
    parent[i] := NULL
end for
d[source] := 0
for i from 1 to n-1
    flag := false
    for all edges from (u,v) in Graph
        if d[u] + cost[u][v] < d[v]
            d[v] := d[u] + cost[u][v]
            parent[v] := u
            flag := true
        end if
    end for
    if flag == false
        break
end for
for all edges from (u,v) in Graph
    if d[u] + cost[u][v] < d[v]
        Return "Negative Cycle Detected"
    end if
end for
Return d

मुद्रण पथ:

सबसे छोटी पथ को एक शीर्ष पर मुद्रित करने के लिए, हम उसके माता-पिता को तब तक वापस भेज देंगे, जब तक कि हम NULL नहीं पाते हैं और फिर शीर्ष को प्रिंट करते हैं। छद्म कोड होगा:

Procedure PathPrinting(u)
v := parent[u]
if v == NULL
    return
PathPrinting(v)
print -> u

जटिलता:

चूंकि हमें किनारों को अधिकतम (वी -1) बार आराम करने की आवश्यकता है, इस एल्गोरिथ्म की समय जटिलता ओ (वी * ई) के बराबर होगी जहां ई किनारों की संख्या को दर्शाता है, अगर हम ग्राफ का प्रतिनिधित्व करने के लिए adjacency list का उपयोग करते हैं। हालांकि, यदि adjacency matrix का उपयोग ग्राफ का प्रतिनिधित्व करने के लिए किया जाता है, तो समय जटिलता O (V ^ 3) होगी । कारण यह है कि हम सभी किनारों के माध्यम से O (E) समय में पुनरावृत्ति कर सकते हैं जब adjacency list का उपयोग किया जाता है, लेकिन जब adjacency matrix का उपयोग किया जाता है तो O (V ^ 2) समय लगता है।

हमें अधिकांश (V-1) समय में सभी किनारों को आराम करने की आवश्यकता क्यों है

इस उदाहरण को समझने के लिए, बेलमैन-फोर्ड एकल स्रोत सबसे छोटे पथ एल्गोरिथ्म पर एक संक्षिप्त विचार रखने की सिफारिश की गई है जो यहां पाया जा सकता है

बेलमैन-फोर्ड एल्गोरिदम में, सबसे छोटा रास्ता खोजने के लिए, हमें ग्राफ़ के सभी किनारों को आराम करने की आवश्यकता है। यह प्रक्रिया अधिकतर (V-1) बार दोहराई जाती है, जहां V ग्राफ में वर्टिस की संख्या है।

स्रोत से अन्य सभी चक्करों के लिए सबसे छोटा रास्ता खोजने के लिए आवश्यक पुनरावृत्तियों की संख्या उस क्रम पर निर्भर करती है जिसे हम किनारों को आराम करने के लिए चुनते हैं।

आइए एक उदाहरण देखें:

यहां, स्रोत शीर्ष 1 है। हम स्रोत और अन्य सभी शीर्षों के बीच की सबसे छोटी दूरी का पता लगाएंगे। हम स्पष्ट रूप से देख सकते हैं कि, सबसे खराब स्थिति में, शीर्ष 4 पर पहुंचने के लिए, इसे (V-1) किनारों पर ले जाना होगा। अब जिस क्रम में किनारों की खोज की गई है, उसके आधार पर, यह शीर्ष 4 की खोज में (V-1) बार लग सकता है। नहीं मिला? यहाँ सबसे छोटा रास्ता खोजने के लिए बेलमैन-फोर्ड एल्गोरिथ्म का उपयोग करते हैं:

हम इस क्रम का उपयोग करने जा रहे हैं:

+--------+--------+--------+--------+
| Serial |    1   |    2   |    3   |
+--------+--------+--------+--------+
|  Edge  |  3->4  |  2->3  |  1->2  |
+--------+--------+--------+--------+

हमारी पहली यात्रा के लिए:

1. d [३] + लागत [३] [४] = अनंत । यह कुछ भी नहीं बदलेगा।
2. d [२] + लागत [२] [३] = अनंत । यह कुछ भी नहीं बदलेगा।
3. d [१] + लागत [१] [२] = २ < d [२] । d [२] = २ । जनक [२] = १ ।

हम देख सकते हैं कि हमारी छूट प्रक्रिया केवल d [2] बदल गई। हमारा ग्राफ ऐसा दिखेगा:

दूसरा पुनरावृत्ति:

1. d [३] + लागत [३] [४] = अनंत । यह कुछ भी नहीं बदलेगा।
2. d [२] + लागत [२] [३] = ५ < d [३] । d [३] = ५ । जनक [३] = २।
3. इसे बदला नहीं जाएगा।

इस बार विश्राम की प्रक्रिया में परिवर्तन किया गया [3] । हमारा ग्राफ ऐसा दिखेगा:

तीसरा पुनरावृत्ति:

1. घ [3] + लागत [3] [4] = 7 <घ [4]। d [४] = 7 । जनक [४] = ३ ।
2. इसे बदला नहीं जाएगा।
3. इसे बदला नहीं जाएगा।

हमारे तीसरे पुनरावृत्ति ने अंततः 1 से 4 तक का सबसे छोटा रास्ता खोज लिया। हमारा ग्राफ ऐसा दिखेगा:

तो, सबसे छोटा रास्ता खोजने के लिए 3 पुनरावृत्तियों को लिया। इस एक के बाद, चाहे हम कितनी भी बार किनारों को आराम करें, घ [] में मान समान रहेंगे। अब, यदि हम एक और अनुक्रम मानते हैं:

+--------+--------+--------+--------+
| Serial |    1   |    2   |    3   |
+--------+--------+--------+--------+
|  Edge  |  1->2  |  2->3  |  3->4  |
+--------+--------+--------+--------+

हमें मिलेगा:

1. d [१] + लागत [१] [२] = २ < d [२] । d [२] = २ ।
2. d [२] + लागत [२] [३] = ५ < d [३] । d [३] = ५ ।
3. घ [3] + लागत [3] [4] = 7 <घ [4]। d [४] = ५ ।

हमारे बहुत पहले पुनरावृत्ति ने स्रोत से अन्य सभी नोड्स के लिए सबसे छोटा रास्ता पाया है। एक और अनुक्रम 1-> 2 , 3-> 4 , 2-> 3 संभव है, जो हमें 2 पुनरावृत्तियों के बाद सबसे छोटा रास्ता देगा। हम इस निर्णय पर आ सकते हैं कि हम क्रम की व्यवस्था कैसे करें, इस उदाहरण में स्रोत से सबसे छोटा रास्ता खोजने के लिए 3 पुनरावृत्तियों से अधिक नहीं लगेगा।

हम यह निष्कर्ष निकाल सकते हैं कि सबसे अच्छे मामले के लिए, स्रोत से सबसे छोटा रास्ता खोजने के लिए 1 पुनरावृत्ति ले जाएगा। सबसे खराब स्थिति के लिए, यह (V-1) पुनरावृत्तियों को ले जाएगा, यही कारण है कि हम विश्राम (V-1) बार की प्रक्रिया को दोहराते हैं ।

एक ग्राफ में नकारात्मक चक्र का पता लगाना

इस उदाहरण को समझने के लिए, बेलमैन-फोर्ड एल्गोरिथ्म के बारे में एक संक्षिप्त विचार रखने की सिफारिश की गई है जो यहां पाया जा सकता है

बेलमैन-फोर्ड एल्गोरिथ्म का उपयोग करके, हम यह पता लगा सकते हैं कि क्या हमारे ग्राफ में कोई नकारात्मक चक्र है। हम जानते हैं कि, सबसे छोटे मार्ग का पता लगाने के लिए, हमें ग्राफ़ के सभी किनारों (V-1) समय को आराम करने की आवश्यकता है, जहाँ V एक ग्राफ़ में वर्टिस की संख्या है। हमने पहले ही देखा है कि इस उदाहरण में , (V-1) पुनरावृत्तियों के बाद, हम d [] को अपडेट नहीं कर सकते, चाहे हम कितने भी पुनरावृत्तियों करें। या हम कर सकते हैं?

यदि किसी ग्राफ में नकारात्मक चक्र है, तो (V-1) पुनरावृत्तियों के बाद भी, हम d [] को अपडेट कर सकते हैं। ऐसा इसलिए होता है क्योंकि प्रत्येक पुनरावृत्ति के लिए, ऋणात्मक चक्र से गुजरना हमेशा कम से कम मार्ग की लागत को कम करता है। यही कारण है कि बेलमैन-फोर्ड एल्गोरिथ्म (वी -1) की पुनरावृत्तियों की संख्या को सीमित करता है। अगर हमने यहां दिक्जस्ट्रा के एल्गोरिथ्म का उपयोग किया है, तो हम एक अंतहीन लूप में फंस जाएंगे। हालांकि, चलो नकारात्मक चक्र खोजने पर ध्यान केंद्रित करते हैं।

मान लेते हैं, हमारे पास एक ग्राफ है:

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

इस तरह ग्राफ (V-1) = 3 पुनरावृत्तियों के बाद दिखता है। यह परिणाम होना चाहिए क्योंकि 4 किनारे हैं, हमें सबसे कम पथ का पता लगाने के लिए अधिकतम 3 पुनरावृत्तियों की आवश्यकता है। तो या तो यह जवाब है, या ग्राफ में एक नकारात्मक वजन चक्र है। यह पता लगाने के लिए कि (V-1) पुनरावृत्तियों के बाद, हम एक और अंतिम पुनरावृत्ति करते हैं और यदि दूरी कम होती रहती है, तो इसका मतलब है कि निश्चित रूप से ग्राफ में एक नकारात्मक भार चक्र है।

इस उदाहरण के लिए: यदि हम 2-3 की जांच करते हैं, तो d [2] + लागत [2] [3] हमें 1 देगा जो d [3] से कम है। इसलिए हम यह निष्कर्ष निकाल सकते हैं कि हमारे ग्राफ में एक नकारात्मक चक्र है।

तो हम नकारात्मक चक्र का पता कैसे लगाते हैं? हम बेलमैन-फोर्ड प्रक्रिया में थोड़ा संशोधन करते हैं:

Procedure NegativeCycleDetector(Graph, source):
n := number of vertices in Graph
for i from 1 to n
    d[i] := infinity
end for
d[source] := 0
for i from 1 to n-1
    flag := false
    for all edges from (u,v) in Graph
        if d[u] + cost[u][v] < d[v]
            d[v] := d[u] + cost[u][v]
            flag := true
        end if
    end for
    if flag == false
        break
end for
for all edges from (u,v) in Graph
    if d[u] + cost[u][v] < d[v]
        Return "Negative Cycle Detected"
    end if
end for
Return "No Negative Cycle"

इस तरह से पता चलता है कि ग्राफ में कोई ऋणात्मक चक्र है या नहीं। हम नकारात्मक चक्रों पर नज़र रखने के लिए बेलमैन-फोर्ड एल्गोरिथम को भी संशोधित कर सकते हैं।