مسئله کوتاه ترین مسیر با لحاظ مسیرهای ممنوعه

مابه یکنوع ازمساله کوتاهترین مسیرمقید که درآن قیدها عبارتنداز این که یک مجموعه از مسیرهای ممنوع دنباله های یالی نمی توانند قسمتی از راه حل امکان پذیر باشند می پردازیم دوروش حل برای اینگونه مسائل ارایه شده است درروش اول الگوریتم تطابقی Aho Corasick را برای فیلترکردن مسیرهایتولید شده بوسیله الگوریتم k-shortest path بکارمی رود درروش دوم شیوه انحراف مسیر مارتینز Martins برای مسیر path k-shortest به وسیله ادغام گراف اصلی با حالت گراف به دست آمده از الگوریتم Aho ٍ Corasick تعمیم داده می شود مانند رویکرد مارتینز مقادیر روش دوم به کاهش چندجمله ای مساله کوتاهترین مسیر با راه ممنوعه بهمساله کوتاهترین مسیر کلاسیک منجر می شود.