Skip to main content
10 of 11
deleted 6963 characters in body

Given a digraph and a root, find a tree that minimizes the sum of edges

I want to find a mathematical formulation to use with the GLPK software package. Given a directed graph and a root, I need to find a tree that minimizes the value of the edges in that graph. Note that we DON'T need to include all vertices.

Instance: a directed graph $G = (V, A)$ with weights $w_a\in\mathbb{R}$ on the edges and a root $v\in V$.
Solution: A directed tree with root $v$.
Objective: Minimize total weight.