گراف جهت‌دار ‎$G$‎ داده‌شده‌است. می‌خواهیم از راس ‎$s$‎ به راس ‎$t$‎ برویم‎‌:‎

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

• سوال قبل