ارائه یک الگوریتم دوگانی برای حل مسائل شبکه جریان با کمترین هزینه

در این مقاله یک الگوریتم جدید برای مسئله معروف جریان با کمترین هزینه مطرح می‌کنیم که با الگوریتم شناخته شده اورلین که دارای مرتبه زمانی چند‌جمله‌ای است متناظر است و همان پیچیدگی زمانی O(m log m (m+n log n) را دارد. m و n بترتیب تعداد راس‌ها و تعداد یال‌ها را نشان می‌دهد. این الگوریتم در مقایسه با الگوریتم اورلین مستقیما با ظرفیت شبکه کارکرده (الگوریتم اورلین هر مسئله را به مسئله حمل و نقل تبدیل می‌کند) و مسئله‌های کلی بیشتری را دربرمی‌گیرد و از نظر عملی موثرتر است، همچنین با استفاده از الگوریتم برش حذفی، پیچیدگی این رده از الگوریتم‌ها را بهبود می‌دهد. بعبارت دیگر این الگوریتم مسئله دوگان سیمپلکس شبکه را به گونه دیگری بررسی می‌کند.

کلیدواژه ها:

مسئله جریان با کمترین هزینه ، الگوریتم‌های دوگان ، برش حذفی ، دوگان سیمپلکس شبکه