کوتاه‌ترین مسیر با اجازه‌ی وزن منفی، با relax کردن همه‌ی یال‌ها تا V بار، با هزینه O(V·E).

اگر دور V‌ام هم فاصله‌ای را بهتر کند، یک دور منفی از مبدأ در دسترس است.