بهبود الگوریتم مستطیلی برای تعیین دور منفی در شبکه های کوتاه ترین مسیر بادور (IIEC 2017)

برای تعیین دور منفی در شبکه های کوتاه ترین مسیر بادور که در آن یک دور منفی وجود دارد الگوریتم های مختلفی وجود دارد،که تمام آنها بر پایه الگوریتم های موجود برای شبکه های کوتاه ترین مسیر بدون دور منفی طراحی شدهاند. مساله تعیین دور منفیعبارتست از یک مساله تصمیم گیری برای وجود یک سیکل منفی در یک شبکه جهت دار در این مساله نیازی به یافتن مسیری از گره sبه گره t نیست زیرا این یک مساله تصمیم گیری است و فقط نیازمند پاسخ بله یا خیر دارد.دراین مقاله، به بهبود الگوریتم مستطیلی برای تعیین دور منفی در شبکه های کوتاه ترین مسیر بادور و همچنین محاسبه پیچیدگیزمانی الگوریتم در بهترین و بدترین حالت و نیز پیدا کردن وزن دور منفی می پردازد که این خود می تواند یک مزیت بزرگ در حوزهآموزشی محسوب شود. در پایان مقاله، الگوریتم جدید در قالب یک مثال نمونه پیاده سازی می شود.

کلیدواژه ها:

الگوریتم فلوید وارشال ، الگوریتم مستطیلی ، شبکه های کوتاه ترین مسیر با دور ، شبکه های کوتاهترین مسیر با دور منفی