مسیرِ بحرانی در یک گرافِ پیش‌نیاز، مسیرِ با بیشترینِ مجموعِ مدت است؛ صرفاً طولانی‌ترین فهرستِ نامِ کارها نیست. اگر منابعِ موازی نامحدود فرض شوند، زمانِ پایانِ زودترینِ پروژه از همین وابستگی و مدت‌ها به دست می‌آید. این تمرین ES وEF و شاهدِ مسیر را می‌سازد و فرضِ منابع را آشکار نگه می‌دارد.
گرافِ معلوم را با مدت کامل کنیم
کارهایِ A،B،C،D وE مدت‌هایِ ۳،۲،۴،۱ و۲ دارند. یال‌هایِ A→C،B→C،C→D وB→E یعنی مبدأ باید پیش از مقصد تمام شود. واحدِ زمان آموزشی است؛ زمانِ اجرایِ مدل یا کارِ واقعیِ مشتری اندازه‌گیری نشده است.
ترتیبِ توپولوژیک، رعایتِ پیش‌نیاز را ممکن می‌کند، اما جایگاهِ سومِ فهرست لزوماً زمانِ شروعِ سه نیست. مدتِ کارها نیز بخشی از داده است. در این مدل، هر کار به محضِ تمام‌شدنِ همهٔ پیش‌نیازها می‌تواند شروع شود؛ محدودیتِ تعدادِ عامل یا دستگاه نداریم.
شروع از بیشترینِ پایانِ پیش‌نیازها
ES یا زودترین شروع، بیشترینِ EFِ پیش‌نیازهاست؛ برای کارِ بدونِ پیش‌نیاز صفر است. EF از ES به‌علاوهٔ مدتِ همان کار ساخته می‌شود. جمع‌کردنِ مدتِ تمامِ پیش‌نیازهایِ موازی، به جایِ بیشینه‌گرفتن، مدلِ دیگری می‌سازد.
| کار | ES | مدت | EF |
|---|---|---|---|
| A | ۰ | ۳ | ۳ |
| B | ۰ | ۲ | ۲ |
| C | ۳ | ۴ | ۷ |
| D | ۷ | ۱ | ۸ |
| E | ۲ | ۲ | ۴ |
C باید هر دو A وB را منتظر بماند؛ پایانِ دیرترِ آن‌ها۳ است، نه مجموعِ ۵. پایانِ پروژه بزرگ‌ترین EF، یعنی۸ است.
عددِ هشت را به یک مسیر وصل کنیم
کد همراهِ بیشینه، پیش‌نیازِ منتخب و مسیرِ منتهی به هر کار را هم نگه می‌دارد. برای D، شاهد A→C→D با مجموعِ ۳+۴+۱=۸ به دست می‌آید. مجموعِ مدتِ همین مسیر دوباره مستقل کنترل می‌شود؛ تنها برچسبِ «بحرانی» بدونِ زنجیره تحویل نمی‌دهیم.
در تساویِ پایانِ دو پیش‌نیاز، شناسهٔ واژگانیِ کوچک‌تر انتخاب می‌شود. این سیاست یکی از شاهدها را قطعی می‌کند، نه اینکه همهٔ مسیرهایِ بحرانی الزاماً یکتا باشند. یک نمونهٔ دارایِ تساوی، یک نمونهٔ با گرهٔ منزوی و یک کارِ مدتِ صفر هم جدا اجرا شده‌اند.
دو ترتیب، یک محاسبهٔ وابستگی
برای گره‌هایِ آماده، یک اجرا ترتیبِ صعودی و دیگری نزولی را انتخاب می‌کند. ترتیبِ پردازش عوض می‌شود ولی EFِ هر کار برابر می‌ماند؛ چون فرمول به پایانِ پیش‌نیازهایِ کامل‌شده وابسته است. این ویژگی برای محاسبهٔ همین مدلِ بدونِ محدودیتِ منابع کنترل شده است.
oracle همهٔ مسیرهایِ گرافِ کوچک را با DFS مستقل می‌شمارد و مجموعِ مدتِ هر مسیر را از دادهٔ اصلی می‌گیرد. بیشترینِ مسیرِ منتهی به هر گره با EF آن برابر است. تمامِ ۶۴گرافِ دارایِ یالِ رو‌به‌جلو روی چهار گره نیز با هر دو ترتیب وoracleِ مسیرها اجرا شده‌اند.
اگر فقط یک منبع داشته باشیم چه؟
جمعِ مدتِ همهٔ کارهایِ مثال۱۲ است. اگر فقط یک منبع،همهٔ کارها را بدونِ هم‌پوشانی انجام دهد، عددِ ۸ِ مدلِ موازی را نباید زمانِ پایانِ آن برنامه نامید. یافتنِ تقویمِ واقعیِ منابع، اطلاعات و قیودِ دیگری می‌خواهد؛ این کد کارهایِ واقعی را اجرا نمی‌کند.
چرخه،مدتِ منفی،مدتِ بولین،مقصدِ ناشناخته،یالِ تکراری و مجموعهٔ خالی در شش آزمون رد می‌شوند. دامنهٔ محلی۱تا۶کار و مدتِ صحیحِ صفر تا۱۰ است. کد، روشِ آموزشیِ مستقیمِ روی گره‌هاست؛ کاهشِ گرافِ دوبخشی و Javaِ منبع اجرا نشده‌اند.
مرتب‌سازیِ توپولوژیک فقط ترتیبِ سازگار می‌دهد و زمان‌بندیِ وزنیِ بازه‌ها زیرمجموعه انتخاب می‌کند. اینجا همهٔ کارهایِ معتبر با مدتِ معلوم تحلیل می‌شوند. ادامه در مبانی هوش مصنوعی؛ شاهدِ این مثال،سرعتِ محصول یا ظرفیتِ اجراییِ اپرا نیست.
فایل تمرین و منبع
کد مستقلِ تمرین و کنترل‌ها؛ Python · تمامِ ورودی‌ها و نتیجهٔ اجرای واقعیِ تمرین؛ JSON
منابع در 2026-11-04 خوانده شدند؛ این تاریخ، تاریخ انتشار منبع نیست. مثال‌ها و فایل‌های این راهنما آموزشی و ساختهٔ تحریریه‌اند.