یک گراف جهتدار وزندار G با مجموعهی رئوس V(G) و مجموعهی یالهای E(G) داریم. یال جهتدار از u به v را با (u,v) نشان میدهیم. وزن یال از u به v را w(u,v) تعریف میکنیم. به یک زیرگراف H از گراف G، MSTr گوییم؛ هرگاه گراف زمینهی H درخت باشد و در H از r به تمام رئوس G مسیر جهتدار وجود داشته باشد و مجموع وزن یالهای H کمینه باشد. f(G,r) برابر با مجموع وزن یالهای MSTr در گراف G است. میخواهیم f(G,r) را پیدا کنیم. «ادموند» الگوریتم بازگشتی زیر را برای این کار ارائه میدهد:
برای هر رأس به جز r مانند v، یال ورودی با وزن کمینه به v را در نظر بگیرید (اگر چند یال با وزن کمینه وجود داشت، یکی را به دلخواه انتخاب میکنیم) و فرض کنید آن یال از رأس π(v) خارج میشود. به زیرگراف با مجموعه رئوس V(G) و مجموعهی یالهای مذکور، H′ میگوییم. اگر در H′ دور جهتدار وجود نداشت، H′ پاسخ مسئله است؛ در غیر این صورت یکی از دورهای H′ را به دلخواه در نظر گرفته و آن را C بنامید. گراف G′ را به روش زیر میسازیم:
V(G′) را برابر {V(G)−V(C)}∪a در نظر میگیریم که a یک رأس جدید است. یالهای G′ را نیز به این صورت میسازیم:
حال الگوریتم را روی G′ اجرا میکنیم تا f(G′,r) به دست آید. مجموع وزن یالهای C را g(C) در نظر میگیریم. در انتها مقدار f(G,r) را f(G′,r)+g(C) اعلام میکنیم.
ثابت کنید الگوریتم ادموند درست کار میکند.