الگوریتم های مسیریابی گراف

[flood1992]

سلام/چند روز پیش استادمون گفت که الگوریتم های مسیر یابی گراف مثل فلویدودایجکستراو...در یه حالته که هیچ موقع جواب نمی دهند.کسی اطلاعاتی در این زمینه داره؟

[مسعود اقدسی فام]

سلام/چند روز پیش استادمون گفت که الگوریتم های مسیر یابی گراف مثل فلویدودایجکستراو...در یه حالته که هیچ موقع جواب نمی دهند.کسی اطلاعاتی در این زمینه داره؟

اگه گراف جهت‌دار باشه ممکنه مسیری وجود نداشته باشه. یا اگه گراف همبند نباشه.

[meisam12]

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

سلام/چند روز پیش استادمون گفت که الگوریتم های مسیر یابی گراف مثل فلویدودایجکستراو...در یه حالته که هیچ موقع جواب نمی دهند.کسی اطلاعاتی در این زمینه داره؟

[19216810047]

میشه توضیح بدید حلقه بی نهایت یعنی چی؟
با تشکر

[meisam12]

توی الگوریتم های مسیریابی وفتی یال های منفی وجود داره امکان داره داره حلقه ای به وجود بیاد که که مجمع وزن یال های آن گراف منفی شود در نتیجه هر دوری که در آن حلقه بزنیم فاصله مسیر را کوتاه تر نشان می دهد و هرگز این حلقه تمام نمی شود
البته الگوریتم های وجود دارد که حلقه منفی را تشخیص می دهد

میشه توضیح بدید حلقه بی نهایت یعنی چی؟
با تشکر