Има ли алгоритъм за изчисляване на най-късото дърво (а не на пътя)? - алгоритъм, графика, дърво, най-кратък път

Поздрави Преливане,

Имам претеглена насочена графика и искамдървото с най-ниски разходи, което обхваща всички възли, където коренът е специфичен даден възел на графиката. Не знам дали мога да задам различно максимално разклонение на всеки възел, където броят на клоните от този възел към други възли (външни ръбове) е равен или по-малък на този максимум?

И така, какъв е най-подходящият алгоритъм за моите нужди да започна да чета? Надявам се, че е достатъчно бърз :)

Много благодаря !

Отговори:

Търсите насочено минимално дърво (arborescence), което е оптимално разклонение.

http://en.wikipedia.org/wiki/Chu%E2%80%93Liu/Edmonds_algorithm