مساله تسريع در كوتاه ترين مسيرهاي متغير زماني با زمان هاي انتظار دلخواه

مسائل شبكه جريان، شاخه حياتي در تحقيق در عمليات هستند. اين مسائل به حالتهاي متغير زماني و ايستا طبقه‌بندي مي‌گردند. مسائل شبكه جريان در كاربردهاي واقعي، متغير زماني هستند، زيرا هر جريان براي عبور از يك كمان بايد يك مقدار زمان داده شده را اتخاذ كند، همچنين همه پارامترها در شبكه مي توانند به جريان وابسته باشد. در اين مقاله، مساله تسريع روي كوتاهترين مسير متغير زماني مطالعه مي گردد. در ابتدا، ما كوتاهترين مسير متغير زماني را توضيح مي‌دهيم. اين مساله يافتن مسيرهايي از يك راس مشخص شده (كه مبدا ناميده مي شود) به ساير رئوس است به‌طوريكه هزينه اين مسير كمترين گردد و مجموع زمان‌هاي عبور و زمان‌هاي انتظار حداكثر T شود، كه T يك عدد صحيح مثبت داده شده است. سپس مساله تسريع براي يك مساله كوتاهترين مسير شرح داده شده است.