سوال 48
حل تشریحی سوال شماره 48 دروس مشترک
کنکور ارشد مهندسی فناوری اطلاعات (IT) 1398
48.
فرض کنید یک گراف وزندار داریم که دور منفی ندارد. برای محاسبه کوتاه ترین مسیر از رأس s و به رأس t از الگوریتم زیر استفاده میکنیم.
همه وزنها را با یک عدد مثبت مناسب x جمع می زنیم تا همگی مثبت شوند. گراف حاصل را مینامیم در با استفاده از الگوریتم دایکسترا کوتاه ترین مسیر از s و به رأس t را محاسبه میکنیم. طول این مسیر جمع وزن یالهای مسیر را منهای تعداد یالها ضربدر x میکنیم و به عنوان خروجی گزارش می دهیم.
در مورد خروجی الگوریتم کدام مورد درست است؟
1)
برابر طول کوتاهترین مسیر از s به t در G است.
2)
حداکثر ۲ برابر طول کوتاه ترین مسیر از S به t در G است.
3)
حداکثر ۴ برابر طول کوتاهترین مسیر از S به t در G است.
4)
میتوان گرافی مثال زد که خروجی الگوریتم حداقل ۱۳۹۸ برابر طول کوتاهترین مسیر از s به t در G است.
پاسخ ها
0 پاسختا کنون پاسخی برای این سوال وارد نشده است،