ماتریس مجاورت با یال منفی

[gm.sara]

سلام
یه سئوالی که برای من پیش آمد اینه که در گراف با یال دارای وزن میشه که وزن یال عددی منفی باشد ؟!

به هر حال بگید اگر وزن یالی منفی بود چه کار باید کرد ؟

ممنون می شم .

[raha_hakhamanesh]

با سلام
به اطلاع شما می رسونم البته می تواند یالهای یک گراف منفی باشد ولی شما نگفتید دقیقا چه کار می خواهید بکنید اما توجه کنید در اینصورت برخی محاسبات تغییر می کند مثلا جستجوی کوتاهترین مسیر در یک گراف که می شه با الگوریتم دیکسترا اون رو بدست آورد دیگه در حالتی که گراف دارای یال منفی باشه درست عمل نمی کنه و بایستی از یک الگوریتم دیگه(در این مورد مثلاً الگوریتم فلوید وارشال) استفاده شود . بهر حال یال می تواند منفی باشد و با توجه به سوال ممکن است راه حل تفاوت کند

[gm.sara]

با تشکر از شما دوست محترم

خوب مثلا همین الگوریتم فلوید را چه تغییری می شه داد که گراف با وزن منفی را محاسبه کنه ؟

[raha_hakhamanesh]

با سلام
الگوریتم فلوید وارشال برای گراف با یال منفی است و وجود یال منفی را تشخیص می دهد ولی اگر دارای دور منفی باشد آنگاه آن را تشخیص می دهد اما گزارش نمی کند .
الگوریتم بلمن-فورد گراف با یال منفی را می پذیرد و چنانچه در گراف دچار دور منفی شویم آن را گزارش می دهد.
الگوریتم جانسون گراف با یال منفی را می پذیرد و دور منفی را نیز گزارش می کند . اما بطور مجانبی سریعتر از فلوید-وارشال است .
اما توجه کنید همه این الگوریتم ها کار جستجو در گراف را انجام می دهند و هدف پیدا کردن کوتاهترین مسیر است اما باید بر اساس تعریف مسئله و نیاز هر یک از آنها را انتخاب کنید چون مرتبه زمانی آنها معمولا بیشتر از n pow(2) است تقریبا نزدیک 3 یعنی برای 100 نقطه (که در مقیاس کاربردی خیلی کم است) تقریبا 1000000 عملیات نیاز است . بنابراین به مرتبه زمانی هریک از الگوریتم های فوق توجه کنید
موفق باشید