۲-
الگوریتم جانسون از دایجکسترا و بلمن فورد به عنوان زیر روال استفاده می کنه و کوتاه ترین مسیر بین دو گره را به شما می ده

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

اگر Bfs رو برای پیدا کزدن کوتاه ترین مسیر در یک گراف جهت دار برای هر گره اجرا کنی زمان نمایی ($O(V^V)$) داری اگر روال اش رو بدون هیج تغییری اجرا کنی .برای بهبود این زمان می تونی در روالش در حین اجرا حلقه اصلی عمل Relaxtion رو انجام بدی تا کوتاه ترین انتخاب بشه یا هر مورد دیگر.
۳-
گراف باید فاقد دور و جهت دار باشه بعد اینکه زمانی یک ترتیب منحصر به فرد بعد از اجرای Topological Sort دارید که گراف همبند باشه و مولفه ناهمبند نداشته باشید اگر راس هایی داشته باشید که همبند ضعیف باشد موقع محاسبه finishing Time آنها باید مشخص کنید که کدام راس اولویت داره برای محاسبتون وگرنه یک ترتیب ندارید.