به یک گراف کامل وزن‌دار ‎$n$‎ رأسی متریک می‌گوییم اگر و فقط اگر به ازای هر سه رأس $u$، $v$ و ‎$w$‎ داشته باشیم ‎$w(u,v)+w(v,w) \geq w(u,w)$‎ که در آن ‎$w(i,j)$‎ وزن یال بین دو رأس ‎$i$‎ و ‎$j$‎ است. یک زیردرخت فراگیر در این گراف را خوب می‌گوییم اگر و فقط اگر وزن کوتاه‌ترین (کم‌وزن‌ترین) مسیر بین هر دو رأس در این درخت حداکثر ‎$n$‎ برابر وزن کوتاه‌ترین مسیر بین همان دو رأس در گراف اصلی باشد.

الگوریتمی از زمان ‎${\cal O}(n^2)$‎ ارائه کنید که با دریافت یک گراف کامل وزن‌دار متریک از ورودی، یک زیردرخت فراگیر خوب در گراف پیدا کند. الگوریتم خود را تحلیل و اثبات کنید.

• سوال بعد
• سوال قبل