حل تشریحی سوال شماره 19 ساختمان داده ها و طراحی الگوریتم ها

کدام گزینه در خصوص دو گزاره (الف) و (ب) به ترتیب درست است؟

الف - به ازای هر گراف G ترتیبی از یالهای گراف وجود دارد که با تنها یک دور ریلکس کردن یالها به آن ترتیب در اجرای الگوریتم بلمن - فورد کوتاه ترین مسیر از رأس s به تمام رأسهای دیگر محاسبه میشوند.

ب - در مرتب سازی ادغامی هر عنصر با O(logn) عنصر دیگر مقایسه میشود.