دور منفی اینه چون می خوای مسیر کمینه را انتخاب کنی اگه که مثلا دو تا یال داشته باشی که ایجاد دور (سیکل) کرده باشن و هزینه این که از شون بگذری منفیه پس وقتی الگوریتم تو دنبال کمترین هزینه است مدام در این دور می چرخه چون هر دفعه به جای این که هزینه عبور از یال اش به مجموع هزینه هاش اضافه کنه این طور ی تازه کم هم می شه .

میشه یه مثال بزنید و حلش کنید؟ جانسونو چی؟ باید بلد باشیم؟

(۰۴ دى ۱۳۹۲ ۰۷:۰۷ ب.ظ)ریحان نوشته شده توسط:  میشه یه مثال بزنید و حلش کنید؟

اینجا مدام در بین ۳ راس اول الگوریتمی که فاقد تشخیص دور منفی باشه می چرخه و هیچوقت به راس ۴ ام نمی ره .

الگوریتم جانسون در واقع میاد با V بار انجام دادن دایکسترا مسئله All pairs shortest path رو حل میکنه به این ترتیب که به راسها میاد یه سری عدد اضاف میکنه که این اعداد با تشکیل یک دستگاه نا معادلات با راس ها بوجود میاره و اگه این دستگاه جواب داشت که اون اعدادی رو که بدست اورده به راس ها اضاف میکنه و روال عادی دایکسترا رو ادامه میده، اگه که اون دستگاه جواب نداشت که این الگوریتم کار نمیکنه، اون دستگاه رو هم میاد با bellman for فکر کنم حل میکنه و مرتبه کلیش میشه فکر کنم[tex]O(V^2\lg V VE)[/tex] اگه صف اولویت توی الگوریتم دایکسترا رو با fibonacci heap بسازی که decrease key اون به صورت سرشکن از مرتبه [tex]O(1)[/tex] هستش.

با عرض شرمندگی شکل باز نمیشه...از بیرونم خیلی ریزه...ممنون که حوصله به خرج دادین