گراف با وزن های منفی (Graph with Negative Weights)، در ریاضیات (Mathematics)
انواع گراف وزن دار (Weighted Graph) را در آموزش زیر شرح دادیم :
گراف با وزن های منفی :
در این نوع خاص، محدودیتی برای مثبت بودن وزن ها وجود ندارد و برخی یال ها یا همه آنها می توانند وزن منفی داشته باشند. این ویژگی، مسائل جدیدی را ایجاد می کند. برای مثال، وزن منفی می تواند نشان دهنده سود یا صرفه جویی در هزینه باشد.
وجود وزن منفی، الگوریتم های کلاسیکی مانند دیکسترا را با مشکل مواجه می کند، زیرا این الگوریتم فرض می کند با اضافه شدن یال های جدید، مسیر هرگز بهتر (کوتاه تر) نمی شود. اما با وزن منفی، این فرض نقض می شود.
برای کار با این گراف ها از الگوریتم بلمن-فورد استفاده می شود. این الگوریتم می تواند وجود چرخه های با وزن منفی (Negative Cycle) را نیز تشخیص دهد. چرخه با وزن منفی چرخه ای است که با طی کردن آن، مجموع وزن ها کاهش یابد. اگر چنین چرخه ای در مسیر دسترسی باشد، مفهوم "کوتاه ترین مسیر" دیگر معنا ندارد، چون می توان بی نهایت بار در این چرخه گشت و مسیر را به هر اندازه که بخواهیم کوتاه تر کرد.
در مدل سازی های مالی، از این گراف ها برای یافتن فرصت های آربیتراژ (Arbitrage) استفاده می شود، جایی که با تبدیل یک ارز به ارزهای دیگر و بازگشت به ارز اول، سود حاصل شود (یافتن چرخه منفی در گراف لگاریتم نرخ های تبدیل).
