سوال 19
حل تشریحی سوال شماره 19 طراحی الگوریتم
کنکور دکتری مهندسی کامپیوتر 1399
19.
فرض کنید G یک گراف وزندار و جهتدار با n رأس و m یال است. با فرض اینکه فاصله کوتاهترین مسیر برای هر دو رأس را در یک ماتریس در اختیار داریم، مطلع شدهایم که وزن تنها یک یال تغییر پیدا کرده است. میخواهیم به ازای دو رأس مشخص s و t طول کوتاهترین مسیر بین این دو رأس را به روز کنیم. این کار را در چه زمانی میتوان انجام داد؟
1)
O(n)
2)
O(n+m)
3)
O(1)
4)
O(nlogn+m)
پاسخ ها
0 پاسختا کنون پاسخی برای این سوال وارد نشده است،