थोड़े बदलाव के साथ बेलमैन-फोर्ड का यह एल्गोरिथम: पंक्ति ७ में, असमानता चिह्न के स्थान पर, हम >= डालते हैं, इसलिए यह बन जाता है: डी [वी]> = डी [यू] + डब्ल्यू (यू, वी)

Bellman-Ford

अब मैं एक तथ्य के लिए जानता हूं कि यह दूरी सरणी को नहीं बदलेगा और यह मुझे एक सही उत्तर देगा। लेकिन यह लाइन 9 पर मेरे पूर्ववर्ती सरणी को कैसे प्रभावित करेगा? क्या यह अभी भी सही उत्तर देगा?

1
Sijaan Hallak 10 नवम्बर 2019, 20:21

1 उत्तर

सबसे बढ़िया उत्तर

यदि आपके पास गैर सकारात्मक किनारे हैं तो यह एक पेड़ नहीं हो सकता है, उदाहरण के लिए निम्नलिखित ग्राफ के लिए और n1 से शुरू:

sample counter example graph

पहले पास में:

  • e1: d[n2] = d[n1] + w[e1] = 1 और p[n2] = n1 पर जाकर
  • e2 पर जाकर: d[n3] = d[n2] + w[e2] = 1 और p[n3] = n2
  • e3 पर जाकर: d[n4] = d[n3] + w[e3] = 1 और p[n4] = n3
  • e4 पर जाकर: d[n2] = d[n4] + w[e4] = 1 और p[n2] = n4

और शेष सभी पासों में, यह दोहराया जाएगा। इसलिए अंत में यदि आप पूर्ववर्ती पर पुनरावृति करते हैं उदाहरण के लिए n2 के लिए आपको मिलेगा: n2 <- n4 <- n3 <- n2 <- n4 <- ...

लेकिन मुझे लगता है कि अगर आपके पास गैर-नकारात्मक किनारे नहीं हैं तो यह ठीक काम करता है।

0
Erfan Loghmani 11 नवम्बर 2019, 15:18