बेलमैन फोर्ड और एक ओलंपियाड प्रश्न?

Question

मैंने तीन दिन पहले ओलंपियाड परीक्षा ली थी। मैं इस प्रकार एक अच्छा सवाल में भाग गया।

हम Bellman- फोर्ड एल्गोरिदम प्रत्येक चरण में सभी किनारों की जाँच जानते हैं, और प्रत्येक बढ़त के लिए अगर,

घ (v)> घ (यू) w + (यू, वी)

तो

d(v) अद्यतन किया जा रहा है कि w(u,v) एज (u, v) और d(u) का वजन वर्टेक्स u के लिए सबसे अच्छा खोज पथ की लंबाई है। यदि एक चरण में हमारे पास no update for vertexes है, तो एल्गोरिदम terminate। k < n के बाद ग्राफ़ जी में वर्टेक्स के साथ ग्राफ़ जी में vertex s से सभी सबसे कम पथ खोजने के लिए, निम्नलिखित में से कौन सा सही है?

1) s से सभी कम से कम पथ में किनारों की संख्या k-1

2) s से सभी कम से कम पथ का वजन अधिक से अधिक अधिक से अधिक k-1

3) ग्राफ़ कोई नकारात्मक चक्र है।

इन विकल्पों पर कौन चर्चा कर सकता है?

Answer 1

1 गलत है, क्योंकि अगर हम सबसे कम पथ के पेड़ के स्थलीय क्रम में आर्क को आराम करने के लिए होते हैं, तो हम इस तथ्य के बावजूद एक पुनरावृत्ति में अभिसरण करते हैं कि सबसे छोटा रास्ता पेड़ मनमाने ढंग से गहरा हो सकता है।

s --> t --> u --> v 

Relax s->t, t->u, u->v; shortest path from s->v is three hops, 
but B--F has made two iterations. 

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

2 गलत है, क्योंकि कौन जानता है कि वजन क्या है?

100 
s --> t 

Relax s->t; weight is 100, but B--F has made two iterations. 

3 सही है, क्योंकि एक औसत तर्क से कम से कम एक नकारात्मक चक्र का एक चाप असंतुलित होगा। v1, ..., vn एक चक्र बनें। चूंकि चापों को आराम दिया जाता है, हमारे पास d(vi) + len(vi->vi+1) - d(vi+1) >= 0 है। सभी i के लिए असमानताएं और d शर्तों को दूर करने के लिए sum_i len(vi->vi+1) >= 0 को सरल बनाने के लिए टेलीस्कोप, जो कहता है कि चक्र अपरिवर्तनीय है।

Answer 2

मुझे लगता है कि विकल्प 3 गलत है क्योंकि यह जानने के लिए कि क्या ऋणात्मक वजन चक्र है, बेलमैन फोर्ड एल्गोरिदम को बार बार चलाने की आवश्यकता है। सबसे पहले पथ की गणना करने के लिए पहले एन -1 बार और फिर सुधार करने के लिए दूरी में कोई सुधार होने के लिए एक और बार, इसका मतलब है कि ऋणात्मक वजन चक्र है।