# Generic tree with minimum weighted path length problem

Suppose there are an undirected graph $G = (V, E)$ and a function $f : V \rightarrow \mathbb{R}$, which associates a weight for each vertex in $G$. I was wondering if it is possible to find a tree $T = (V, E_T)$, where $E_T \subseteq E$ and $\sum_{i \in V} f(i) d_{i}^T$ is minimal. The root of all trees must be a predetermined node $u \in V$ and $d_i^T$ returns the depth of a node $i$ in the tree $T$.

It looks like a tree with minimum weighted path length problem, which could be built using a Huffman tree, but as it turns out Huffman tree is supposed to be binary, but I would like to find a generic tree, whose the degree of the nodes may be more than two.

Has this problem been classified regarding its complexity?

• This just seems like a shortest-path tree – Alexander - Reinstate Monica Sep 5 '17 at 4:02
• It is a shortest-path tree if $f(i) = 1$ for each $i$, but solving with weighted paths doesn't seem as straightforward as finding a SPT. – user12707 Sep 6 '17 at 21:50
• Is f(i) just the edge weight? In that wiki page, they call that dist(u) – Alexander - Reinstate Monica Sep 7 '17 at 3:27
• $f(i)$ is the weight of a generic node $i$. It's noteworthy that I'm trying to minimize $\sum_{i \in V} f(i) d_{i}^T$, where $d_i$ is the depth or the distance from the node $i$ to $u$ (the root of the tree). I'm not sure if SPT or MST could solve that problem. – user12707 Sep 7 '17 at 21:35
• So if I understand correctly, you just have a weight on each node, and a weight on each edge. You're trying to minimize the sum of node/edge weight products on the path from the start node to every end node. Correct? Couldn't a modified version of Dijkstra's algorithm do this? – Alexander - Reinstate Monica Sep 8 '17 at 0:50