... يك ايده برنامه نويسي پويا :
يك روش برنامه نويسي پويا سعي بر حل این مساله براي يافتن كوتاهترين مسير از s به t زمانيكه لبه با وزن منفي داشته باشيم اما سيكل ( دوره ) با طول منفي نداشته باشيم . زر مساله i مي تواند كوتاهترين مسير را تنها بوسيله استفاده از i گره اوليه پيدا كند . این ايده بلافاصله جواب نمي دهد بلكه با اعمال اندكي تغييرات جواب دلخواه را به ما ميدهد . الگوريتم Bellman-Ford algorithm اين الگوريتم را بوسيله برنامه نويسي پويا مطرح كرده و حل كرده اند .
اگر G دورهای منفی نداشته باشد؛‍‍‍ پس کوتاهترین مسیر ساده از S به t وجود دارد.(یعنی گره ها تکرار نمی شوند.) و از اینرو در نهایت n-1 یال دارد.
اثبات: تا زمانی که هر دور هیچ هزینه منفی نداشته باشد؛ کوتاهترین مسیر P از s به t با بیشترین تعداد از یالها هیچ راس v را مرور نمی کند. اگر P ؛ راس v را تکرار کند؛ ما می توانیم بخش مابین عبورهای متوالی از v را حذف کنیم. که این عمل هزینه کمینه و یال بیشینه را نتیجه می دهد.
اجازه دهید OPT(i,v) را برای تفکیک کمترین هزینه یک مسیر v-t با استفاده از بیشترین یال i مورد استفاده قرار دهیم. مطابق مساله (6.22) اصی ترین مشکل؛ محاسبه OPT(n-1.s) است.(ما می توانیم به جای ساخت الگوریتم؛ زیر مسائل مرتبط با کمینه هزینه مسیر s-v را با استفاده از بیشترین یالi جایگزین کنیم. این یک موازی طبیعی با الگوریتم دایجسترا شکل خواهد داد. اما در پروتوکل های مسیر یابی که بعدا شرح خواهیم داد؛ این یک روش طبیعی نخواهد بود.)
اکنون راه ساده ای را برای بیان OPT(i,v) با استفاده از زیرمسائل کوچکتر نیازداریم. ما دیداه طبیعی تری که نکات بسیاری حالات مختلف را در بر می گیرد را مرور خواهیم کرد؛ این مثال دیگری است از اصل "انتخابهای چند مسیره" که در الگوریتم مساله کوچکترین مربعات بخش شده خواهیم دید.
اجازه دهید؛ مسیر بهینه p OPT(i,v) را که در شکل 6.22 نمایش داده شده است را اثبات کنیم...

متن كامل فارسي
ترجمه: محمد رضا فرشچي، هادي خليل پور

آدرس لینک به این مطلب:
http://www.asahand.com/cgi-bin/mt/mt-tb.cgi/48