سلام
دوستان اگر کسی میتونه طریقه پیدا کردن کوتاه ترین مسیر درالگوریتم DGA رو بهم بگه ممنون میشم.
در زیر مراحل انجام این الگوریتمو گذاشتم ولی نمیدونم راهش چطوری؟؟تو کتاب توضیحی درباره روشش نداده.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
سلام دوست عزیز
اگر منظورتون الگوریتم یافتن کوتاه ترین مسیر در گراف dag (گراف جهت دار بدون دور) هست یه این شرح است:
ابتدا به راس S صفر و به بقیه بی نهایت میدهیم سپس ترتیب توپولوژیکی گراف را با استفاده از پیمایش عمقی (DFS) گراف به دست می آوریم سپس به ترتیب راسها در ترتیب توپولوژیکی یالهایی که از هر راس خارج شده را Relax میکنیم.
مرتبه این الگوریتم هم همان مرتبه DFS هست. در این روش یالها میتوانند وزن منفی هم داشته باشند.
میشه تو شکلی که دادم چند تا گامو برام توضیح بدید متوجه بشم؟؟
ممنون میشم اینکارو کنید.
(09 آذر 1392 11:19 ق.ظ)tarane1992 نوشته شده توسط: [ -> ]میشه تو شکلی که دادم چند تا گامو برام توضیح بدید متوجه بشم؟؟
ممنون میشم اینکارو کنید.
بله حتما.
ترتیب توپولوژیکی نودهای گراف همانطور که در شکل مشخص است این هست: r s t x y z
در گام اول S را صفر میدهیم چون نقطه ابتدایی مسیرهاست و بقیه نودها بی نهایت ، این مقدار در واقع distance ابتدایی هر نود هست.
گام دوم: با توجه به ترتیب ذکر شده ابتدا به r و بالهای خارج شده از آن نگاه میکنیم و برای هر یال relax را اجرا میکنیم. r دو یال خروجی دارد relax کردن یال rs: آیا مقدار فعلی S یعنی صفر بزرگتر از بی نهایت + 5 است اگر باشد مقدار بی نهایت + صفر جایگزین مقدار فعلی اش میشود که در اینجا مسلما بزرگتر نیست پس چیزی را تغییر نمیدهیم و به سراغ یال بعدی میرویم که آنرا هم با توجه به مقایسه میفهمیم که نتیجه مقایسه بزرگتر نیست پس تغییری نمیکند.
گام سوم: نود S دو یال خروجی st و sx دارد: relax برای یال st: آیا 0بی نهایت (مقدار فعلی t ) بزرگتر از 0 + 2 هست که هست پس مقدار 0+2 جایگزین مقدار فعلی t میشود ، سپس relax را برای یال sx انجام میدهیم که حاصل اینست که x هم مقدار جدید 6 میگیرد.
سپس در گامهای بعدی را هم در هر گام برای نودهای بعدی به ترتیب یالهای خروجی از هر نود را relax میکنیم.
در نهایت طول کوتاهترین مسیر هر نود از مبدا S مقدار هر نود هست و کار تمام است.
امیدوارم توضیحم مفید باشد.