یک گره بحرانی در مسئله کوتاهترین مسیر گرهای است که با حذف آن بیشترین افزایش هزینه در جواب بهینه جاری رخ دهد . در شبکههای تصادفی بجهت ماهیت تصادفی پارامترهای شبکه و بدنبال آن غیر قطعی بودن اتصالهای ایجاد شده ، معیار جامعتری برای تشخیص یک گره بحرانی نیاز است. با فرض توزیع نمایی برای طول یا لها در یک شبکه جهتدار بدون ،دور گره بحرانی با یک معیار تصادفی تعیین و احتمال رسیدن به گره مقصد از یک گره مبدأ براساس آن محاسبه میگردد. تعمیمی از احتمال کوتاهترین مسیر بودن برای یک مسیر داده شده با توجه به اینکه گرههای آن تا چه حد بحرانی هستند ارائه میشود، بطوریکه میتوان تعیین کرد یک مسیر معین بطور میانگین ت ا چه اندازه بحرانی است.
