مسئله طولانی‌ترین مسیر

یک مسیر زمانی ساده نامیده می‌شود که دارای رئوس تکراری نباشد. بر خلاف مسئله کوتاه‌ترین مسیر که کوتاهترین مسیر بین دو راس را به ما می‌دهد و در زمان چندجمله‌ای حل می‌شود، برای مسئله یافتن طولانی‌ترین مسیر زمان چندجمله‌ای وجود ندارد و جزء مسائل ان‌پی کامل(NP-complete)است. و به این معنی است که در زمان چندجمله‌ای نمی توان برای آن جواب پیدا کرد مگر اینکه P=NP باشد.

واضح است که اگر یک مسیر عمومی معین دارای مسیر Hamiltonian باشد، این مسیر Hamiltonian، بلندترین مسیر احتمالی است، زیرا همه رئوس احتمالی را طی می‌کند. برای حل مسئله Hamiltonian از یک الگوریتم طولانی‌ترین مسیر استفاده می‌کنیم، از این الگوریتم برای حل بلندترین مسیر در یک گراف با ورودی‌های یکسان و مجموعه k=|V|-۱ استفاده می‌کنیم که |V| تعداد رئوس در گراف است.

اگر یک مسیر Hamiltonian در گراف وجود داشته باشد پس الگوریتم yes را برمی گرداند، زیرا مسیر Hamiltonian دارای طول معادل با1-|V| است. بر عکس اگر الگوریتم دارای خروجی yes باشد، یک مسیر ساده با طول 1-|V| در گراف وجود دارد. و چون طول آن |V|-1 است می‌توان نتیجه گرفت که از همه رئوس گراف بدون تکرارگذشته‌است که همان مسیر Hamiltonian است. چون مسئله مسیر Hamiltonian یک مسئله ان پی کامل NP-complete است، این ساده‌سازی اثبات می‌کند که ان‌پی سخت (NP-hard) نیز است. برای اینکه تشان دهیم NP-complete است باید نشان دهیم NP است.

مسئله یافتن طولانی‌ترین مسیر را می‌توان به مسئله یافتن کوتاهترین مسیر کاهش (reduction) داد.(گرچه ممکن است این گراف دارای دور با وزن منفی باشد) اگر گراف ورودی برای مسئله بلندترین مسیر G باشد، کوتاهترین مسیر ساده بر روی گراف Hamiltonian خواهد بود که دقیقاً مشابه G است، اما وزن‌های لبه منفی می‌شود، و بلندترین مسیر بر روی G است. هر چند هر یک از دورها با وزن مثبت در گراف اصلی G منتهی به دورهایی با وزن منفی در گراف Hamiltonian خواهد شد. بنابراین یافتن کوتاه‌ترین مسیر ساده بر روی یک گراف با دورهایی با وزن منفی، نیز ان پی کاملاست. اگر G حاوی هیچ دوری نباشد، پس Hamiltonian هیچ دوری با وزن منفی نخواهد داشت و هر یک از الگوریتم‌های یافتن کوتاه‌ترین مسیر اکنون می‌تواند بر روی Hamiltonian اجرا شوند تا مسئله اصلی در زمان چندجمله‌ای حل شود. بنابراین مسئله بلندترین مسیر بر روی گراف‌های بدون دور ساده‌است.

همانطور که در بالا اشاره شد، مسئله یافتن طولانی‌ترین مسیر بر روی گراف‌های بدون دور را می‌توان در زمان چندجمله‌ای و از طریق منفی کردن وزن یال‌ها و اجرای یک الگوریتم یافتن کوتاه‌ترین مسیر حل کرد.

همانطور که در بالا گفته شد طولانی‌ترین مسیر در گراف‌های بدون دور از طریق معکوس کردن وزن یال‌ها و اجرای الگوریتم‌های پیدا کردن کوتاه‌ترین مسیر در زمان چندجمله‌ای حل کرد. الگوریتمی که در ادامه امده از روش تبدیل قبلی استفاده نمی‌کند و پیچیدگی زمانی بهتری هم دارد.

گراف‌های وزن دار جهت‌دار بی دور

اگر G گراف جهت‌دار غیرمدور باشد، مسئلهٔ یافتن بلندترین مسیر را می‌توان در زمان خطی با استفاده از روشبرنامه نویسی پویا حل کرد. فرض کنید که (toporder(g دارای خروجی یک رشته از رأس‌ها در به صورت توپولوژیکی (که می‌تواند به وسیله یمرتب‌سازی توپولوژیکی انجام شود و این مرحله باید گراف جهت‌دار بدون دور باشد) باشد. بعلاوه، (V(G مجموعه رأس‌های گراف و (E(G مجموعه یال‌های گراف باشد، اگر گراف وزن دار بود وزن خود یال را به کار می‌بریم در غیر این صورت به هر یال یک وزن دلخواه به جز صفر اختصاص می‌دهیم. سپس الگوریتم زیر طول بلندترین مسیر را پیدا می‌کند.

algorithm dag-longest-path is

   input:
        Directed acyclic graph G
   output:
        Length of the longest path

length_to = array with |V(G)| elements of type int with default value 0

 for each vertex v in topOrder(G) do
       for each edge (v, w) in E(G) do
           if length_to[w] <= length_to[v] + weight(G,(v,w)) then
               length_to[w] = length_to[v] + weight(G, (v,w))

   return max(length_to[v] for v in V(G))

مسئلهٔ فروشندهٔ مسافر

سورس الگوریتم

NP-completenes