سلام
ابتدا Topological sort رو اجرا کنید ، سپس موقع Relax کردن بجای انتخاب کمترین وزن ، بیشترین وزن رو به ازای V-1 رئوس از راس ورودی انتخاب کنید با همان هزینه V+E
مساله مشابه که NP-Hard : یافتن طولانی ترین مسیر بین دو راس در یک گراف بدون وزن ، بدون جهت هست.