یک گراف جهت‌دار وزن‌دار $G$ با مجموعه‌ی رئوس $V(G)$ و مجموعه‌ی یال‌های $E(G)$ داریم. یال جهت‌دار از $u$ به $v$ را با $(u, v)$ نشان می‌دهیم. وزن‌ یال از $u$ به $v$ را $w(u, v)$ تعریف می‌کنیم. به یک زیرگراف $H$ از گراف $G$، $MST_r$ گوییم؛ هرگاه گراف زمینه‌ی $H$ درخت باشد و در $H$ از $r$ به تمام رئوس $G$ مسیر جهت‌دار وجود داشته باشد و مجموع وزن یال‌های $H$ کمینه باشد. $f(G, r)$ برابر با مجموع وزن یال‌های $MST_r$ در گراف $G$ است. می‌خواهیم $f(G, r)$ را پیدا کنیم. «ادموند» الگوریتم بازگشتی زیر را برای این کار ارائه می‌دهد:

برای هر رأس به جز $r$ مانند $v$، یال ورودی با وزن کمینه به $v$ را در نظر بگیرید (اگر چند یال با وزن کمینه وجود داشت، یکی را به دل‌خواه انتخاب می‌کنیم) و فرض کنید آن یال از رأس $\pi(v)$ خارج می‌شود. به زیرگراف با مجموعه رئوس $V(G)$ و مجموعه‌ی یال‌های مذکور، $H'$ می‌گوییم. اگر در $H'$ دور جهت‌دار وجود نداشت، $H'$ پاسخ مسئله است؛ در غیر این صورت یکی از دورهای $H'$ را به دل‌خواه در نظر گرفته و آن را $C$ بنامید. گراف $G'$ را به روش زیر می‌سازیم:

$V(G')$ را برابر $\{V(G) - V(C)\} \cup a$ در نظر می‌گیریم که $a$ یک رأس جدید است. یال‌های $G'$ را نیز به این صورت می‌سازیم:

• اگر $(u, v)$ یک یال در $E(G)$ بود؛ طوری که $u \notin C$ و $v \in C$، یک یال در $E(G')$ از $u$ به $a$ با وزن $w(u, v) - w(\pi(v), v)$ می‌گذاریم.
• اگر $(u, v)$ یک یال در $E(G)$ بود؛ طوری که $u \in C$ و $v \notin C$، یک یال در $E(G')$ از $a$ به $v$ با وزن $w(u, v)$ می‌گذاریم.
• اگر $(u, v)$ یک یال در $E(G)$ بود؛ طوری که $u \notin C$ و $v \notin C$، یک یال در $E(G')$ از $u$ به $v$ با وزن $w(u, v)$ می‌گذاریم.

حال الگوریتم را روی $G'$ اجرا می‌کنیم تا $f(G', r)$ به دست آید. مجموع وزن یال‌های $C$ را $g(C)$ در نظر می‌گیریم. در انتها مقدار $f(G, r)$ را $f(G', r) + g(C)$ اعلام می‌کنیم.

ثابت کنید الگوریتم ادموند درست کار می‌کند.

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