گراف جهت‌دار $G$ داده‌شده‌است. می‌خواهیم از راس $s$ به راس $t$ برویم:
الگوریتمی از $O(e)$ ارائه دهید که به عنوان خروجی رئوسی را بدهد که اگر بخواهیم کوتاهترین مسیر بین $s$ و $t$ را طی کنیم، حتما باید از آنها عبور کنیم.
الگوریتمی از $O(e)$ ارائه دهید که به عنوان خروجی رئوسی را بدهد که اگر مجاز باشیم حداکثر یک یال بیش از مسیر کمینه استفاده کنیم، باز هم حتما باید از آنها عبور کنیم.