تالار گفتمان مانشت

سلام.
آیا این دو الگوریتم با وجود دور منفی درست کار میکنند؟؟؟
یه جا خونده بودم که درست کار میکنند ولی متاسفانه الان یادم نمیاد کجا خوندم.

ن فقط بلمن فورد با یال منفی درس کارمیکنه

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

(13 بهمن 1393 01:20 ب.ظ)Sakura نوشته شده توسط: [ -> ]سلام
این مسئله دور منفی بیشتر در الگوریتم های یافتن کوتاهترین مسیر، در یک گراف جهتدار اهمیت پیدا میکنه.
دو الگوریتم پریم و کروسکال روی گراف وزن دار(وزن خواه مثبت باشه خواه منفی) و بدون جهت عمل میکنند و توی یک گراف بدون جهت بیشتر داشتن یا نداشتن دور مهمه(منظورم اینه که مهم نیست دور منفی باشه یا مثبت) و هر دو الگوریتم پریم و کروسکال در هر مرحله چک میکنند که یالی که قراره به مجموعه جواب اضافه بشه ایجاد دور نکنه(حالا میخواد دور منفی باشه یا مثبت، این مهم نیست مهم ایجاد نشدن دور هست) پس میشه گفت که کلا این دو تا الگوریتم دور رو تشخیص می دهند(فرقی نداره دور مثبت باشه یا منفی)
این مسئله منفی بودن دور بیشتر تو گراف جهتدار اهمیت پیدا میکنه، مثلا الگوریتم هایی مثل بلمن فورد یا دیجسترا که روی یک گراف وزن دار و جهتدار عمل میکنند تا کوتاهترین مسیر رو پیدا کنند، اینکه بتونن دور منفی رو تشخیص بدن خیلی اهمیت داره چون وجود دور منفی باعث میشه فاصله بین دو راس منفی بی نهایت بشه.

درسته
منم نظرم همینه.
چون که توی هر مرحله وجود دور چک میشه ، مشکلی پیش نمیاد و درست کار میکنن.