یک مشکل متداول در سفره های هوایی هنگامی که پرواز مستقیم وجود نداشته باشد تعیین کوتاه ترین مسیر پرواز از شهری به شهر دیگر است .
حال الگوریتمی طراحی می کنیم که این مسئله و مسائل مشابه را حل کند .
نخست لازم است نظریه گراف ها را مرور کنیم .
شکل یک گراف جهت دار و موضون را نشان می دهد به خاطر دارید که در نمایش تصویری گراف ها دایره نشان گر راس ها و خط میان دو دایره نشان دهنده یال ها هستند .
اگر هر یال دارای جهت باشد گراف را گراف جهت دار یا دیاگراف می گویند .
هنگام رسم یال ها در این گونه گراف ها از پیکان برای نشان دادن جهت استفاده می کنیم در یک دیاگراف بین دو راس امکان وجود دو یال است که جهت آنها مخالف هم هست.
برای مثال درشکل یک یال از v1 به v2 و یکی از v2 به v1 وجود دارد.اگر این یال ها با مقادیری همراه باشند این مقادیر را وزن و گراف حاصل را موزون می خوانند.
در این جا فرض می کنیم که این مقادیر غیر منفی است.گرچه این مقادیر را معولاً وزن می نامند در بسیاری از از کابردها نشانگر فاصله است.بنابراین مسیر را به عنوان فاصله میان راسی تا راس دیگر در نظر می گیرند.در یک گراف جهت دار مسیر مجموعه ای از راس هاست به طوری که از یک راس تا راس دیگر یک یال وجود دارد.
مسیری از یک راس به خود آن راس را چرخه می گویند.
اگر مسیری هیچگاه دوبار از یک راس نگذرد مسیر ساده نامیده می شود.توجه کنید که یک مسیر ساده هرگز حاوی زیر مسیری که چرخه ای باشد نیست.طول یک مسیر در گراف موزون حاصل جمع اوزان مسیر است.
در یک گراف ناموزون طول مسیر صرفاً عبارت است از تعداد رئوس موجود در آن است.
مسئله ای که کاربردهای فراوان دارد یافتن کوتاهترین مسیر از راسی به رئوس دیگر است.
واضح است کوتاهترین مسیر باید مسیری ساده باشد.
در شکل سه مسیر ساده از v1 به v2 وجود دارد یعنی [v1,v2,v3] [v1,v4,v3] [v1,v2,v4,v3] .چون
Length[v1,v2,v3]=1+3=4
Length[v1,v4,v3]=1+2=3
Length[v1,v2,v4,v3]=1+2+2=5
[v1,v4,v3]کوتاهترین مسیر ازv1 به v3 است.همانطور که پیش از این گفته شد یک کاربرد متداول کوتاهترین مسیر تعیین کوتاهترین مسیر میان دو شهر است.
مسئله کوتاهترین یک مسئله بهینه سازی است.
برای هر نمونه از مسئله بهینه سازی ممکن است بیش از یک راه حل وجود داشته باشد.هریک از راه حل های پیشنهادی دارای مقداری مرتبط با آن است و حل نمونه آن حلی است که دارای مقدار بهینه است.مقدار بهینه حداقل است یا حد اکثر در مورد مسئله کوتاهترین مسیر یک حل پیشنهادی مسیری از یک راس به راس دیگر بود .مقدار آن طول مسیر و مقدار بهینه حداقل طول است.
چون ممکن است بیش از یک کوتاهترین مسیر از راسی به راس دیگر وجود داشته باشد مسئله ما یافتن هر یک از این کوتاهترین مسیر هاست.یک الگوریتم واضح برای این مسئله تعیین طول همه مسیرها برای هر راس از ان راس به هریک از رئوس دیگر است.اما زمان این الگوریتم بدتر از زمان نمایی است.
برای مثال فرض کنید از هر راس به همه رئوس دیگر یک یال وجود دارد .در این صورت زیر مجموعه ای از همه مسیر ها عبارت است از مجموعه ای خواهد بود که از راس نخست شروع می شود و به راسی دیگر ختم می شود و از همه رئوس دیگر عبور می کنند.چون راس دوم در چنین مسیری می تواند هریک از n-2 راس باشد راس سوم در چنین مسیری می تواند هر یک از n-3 راس باشد...
و راس دومی به آخری روی چنین مسیری فقط می تواند یک راس باشد.تعداد کل مسیرها از یک راس که از همه رئوس دیگر بگذرد عبارت است از :
(n-2)(n-3)…1=(n-2)!
که بد تر از حالت نمایی است.
در بسیاری از مسائل بهینه سازی با همین وضعیت مواجه هستیم .
یعنی الگوریتمی که همه حالت های ممکن را در نظر بگیرد زمان آن نمایی یا بدتر است.
با استفاده از برنامه نویسی پویا یک الگوریتم زمانی درجه سوم برای مسئله کوتاهترین مسیر ایجاد می کنیم.
نخست الگوریتمی طرح می کنیم که فقط طول کوتاهترین مسیرها را تعیین کند.
سپس آن را طوری اصلاح می کنیم که کوتاهترین مسیر را نیز ایجاد کند .یک گراف موزون حاوی n راس را با یک آرایه w نشان می دهند که در آن
اگر یالی بین , باشد وزن یال اگر یالی بین , نباشد w[i][j]= اگر i=j باشد 0 چون راس vj وقتی مجاور راس vi خوانده می شود که یالی بین vj و vi باشد به این آرایه نمایش ماتریس همجواری یک گراف می گویند .اگر بتوانیم راهی برای محاسبه مقادیر d از مقادیر w بیابیم الگوریتمی برای مسئله کوتاهترین مسیر خواهیم داشت این هدف با ایجاد n+1 آرایه قابل حصول است که وداریم : =طول کوتاهترین مسیر از VI به VJ فقط با استفاده از رئوس موجود در مجموعه {V1,V2,….VK} به عنوان رئوس واسطه پیش از انکه نشان دهیم چرا به این ترتیب قادر به محاسبه D از روی W هستیم معنی عناصر این آرایه ها را توضیح می دهیم .
مثال چند مقدار از را به عنوان مثال برای گراف شکل حل می کنیم.
برای هر گراف اینها مساویند زیرا کوتاهترین مسیری که از v2 آغاز می شود نمی تواند از v2 بگذرد برای این گراف ها اینها مساویند زیرا با گنجاندن v3 مسیر جدیدی از v2 به v5 بدست نمی آید .
برای هر گراف اینها مساویند زیرا کوتاهترین مسیری به v5 منتهی می شود نمی تواند از v5 بگذرد.
آخرین مقدار محاسبه شده طول کوتاهترین مسیر از V2 به V5 است که مجاز به عبور از هر یک از رئوس دیگر است .یعنی طول کوتاهترین مسیر است.
بنابراین برای تعیین D از روی W فقط باید راهی برای بدست آوردن از روی بیابیم.
مراحل استفاده از برنام نویسی پویا برای رسیدن به این هدف عبارت است از : ارائه یک ویژگی (فرایند بازگشتی که با آن بتوان را از روی محاسبه کرد.
حل کردن نمونه ای از مسئله به شیوه جزء به کل با تکرار فرایند (ارائه در مرحله 1) به ازای K=1تاn پس دنباله زیر ایجاد می شود: مرحله یک را با در نظر گرفتن دو حالت به انجام می رسانیم.
مورد 1: حداقل یک نمونه از کوتاهترین مسیر بین VI,VJ با استفاده از تنها رئوس {V1,V2,….VK} به عنوان رئوس واسطه از VK استفاده نمی کند در این صورت داریم : زیرا هنگامی که راس V5 را هم می گنجانیم کوتاهترین مسیر از V1 به V3 هنوز [V1,V4,V3] است.
مورد2: همه نمونه های کوتاه ترین مسیر میان Vi,Vj که فقط از رئوس موجود در {V1,V2,…Vk}به عنوان رئوس واسطه استفاده می کند از Vk نیز استفاده می کنند.
در این مورد هر یک از کوتاهترین مسیر ها ظاهری نظیر شکل 4-3 دارد.
چون VK نمی تواندیک راس واسطه روی زیر مسیری از Vi بهVk باشد آن زیر مسیر فقط از رئوس موجود در {V1,V2…,Vk-1} به عنوان واسطه استفاده می کند.
این بدان معناست که طول مسیر به دلایلی که در ادامه خواهد آمد برابر است: دلیل اول این است که طول زیر مسیر نمی تواند کوتاهتر باشد زیرا طول کوتاهترین مسیر از V1 به Vk فقط از رئوس موجود در {V1,V2,…Vk-1}به عنوان رئوس میانی استفاده می کند.
دوم این که طول زیر مسیر نمی تواند بیشتر باشد زیرا اگر بود می شد یکی از کوتاهترین مسیر ها را جایگزین آن کرد واین خلاف این واقعیت است که کل مسیر کوتاهترین مسیر است.
به طور مشابه طول زیر مسیر ازVk به Vj باید مساوی باشد بنابراین در مورد دوم : مثالی از مورد دوم عبار ت است از: چون باید یکی از دو مورد 1 یا 2را داسته باشیم مقدار حداقل مقادیر طرف راست تساوی ها است یعنی می توانیم را به صورت زیر از روی تعیین کنیم.
در طرح الگوریتم برنامه نویسی پویا به مرحله1 دست پیدا کرده ایم برای دست یابی به مرحله 2 از ویژگی بازگشتی مرحله 1 برای ایجاد دنباله از آرایه های نشان داده شده در رابطه (2-3) استفاده می کنیم .حال مثالی را حل کنیم تا نشان دهیم هر یک از این آرایه ها چگونه از روی قبلی محاسبه می شود.
مثال با داشتن گراف 3-2 که توسط مانریس هم جواری W نشان داده شده است چند مثال به صورت زیر محاسبه شده اند(به خاطر داشته باشید کهاست: